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 …