Give the number of possible strings (modulo 1e9+7) of length N satisfying following constraints:
- string should contain only letters G, O , A and T
- it should not contain ‘AOT’ as a sub-string
- swapping any two adjacent letters in string should not violate the above two conditions
Constraints:
3 <= N <= 100
Sample Test 1:
Input
3
Output
61
Sample Test 2:
Input
4
Output
230
Could you please provide the approach for solving this problem …