As we all know adkroxx is a great programmer of our institute. But due to programming he started missing a lot of classes. Now the institute decides to offer him cash reward for good attendance. If he is absent for 4 consecutive days or late on more than one occasion they will forfeit his prize. During an $n$-day period a ternary string is formed for each day consisting of $L$'s (late), $O$'s (on time), and $A$'s (absent).

Adk being a smart kid tries to find out what is the total number of prize string that exists. Although there are eighty-one ternary strings for a $4$-day period that can be formed, exactly forty-seven strings would lead to a prize.

Now you have to help adkroxx to find out number of prize strings for $n = 10000007$ and report the

answer modulo $10^9+7$.