Score : 400 points
You are given an integer N. Find the number of strings of length N that satisfy the following conditions, modulo 10^9+7:
A
, C
, G
and T
.AGC
as a substring.A substring of a string T is a string obtained by removing zero or more characters from the beginning and the end of T.
For example, the substrings of ATCODER
include TCO
, AT
, CODER
, ATCODER
and (the empty string), but not
AC
.
Input is given from Standard Input in the following format:
N
Print the number of strings of length N that satisfy the following conditions, modulo 10^9+7.
3
61
There are 4^3 = 64 strings of length 3 that do not contain characters other than A
, C
, G
and T
. Among them, only AGC
, ACG
and GAC
violate the condition, so the answer is 64 - 3 = 61.
4
230
100
388130742
Be sure to print the number of strings modulo 10^9+7.