### Problem

After the king’s speech , everyone is encouraged. But the war is not over. The king needs to give orders from time to time. But sometimes he can not speak things well. So in his order there are some ones like this: “Let the group-p-p three come to me”. As you can see letter ‘p’ repeats for 3 times. Poor king!

Now , it is war time , because of the spies from enemies , sometimes it is pretty hard for the general to tell which orders come from the king. But fortunately the general know how the king speaks: the king never repeats a letter for more than 3 times continually .And only this kind of order is legal. For example , the order: “Let the group-p-p-p three come to me” can never come from the king. While the order:” Let the group-p three come to me” is a legal statement.

The general wants to know how many legal orders that has the length of n

To make it simple , only lower case English Letters can appear in king’s order , and please output the answer modulo 1000000007.

We regard two strings are the same if and only if each charactor is the same place of these two strings are the same.

### Analysis

dp[i][j]表示长度为i，最后字符长度为j的合法串。每次把当前串后面加一个字符递推即可。

### Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 2048;
const ll mod = 1000000007;
ll dp[maxn][5];

void init() {
dp[1][1] = 26;
for(int i = 1; i <= 2000; ++i) {
for(int j = 1; j <= 3; ++j) {
if(!dp[i][j]) continue;
if(j < 3) dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]) % mod;
dp[i+1][1] = (dp[i+1][1] + dp[i][j] * 25) % mod;
}
}
}

int main() {
init();
int T; scanf("%d", &T);
while(T--) {
int n; scanf("%d", &n);
ll ans = 0;
for(int i = 1; i <= 3; ++i)
ans = (ans + dp[n][i]) % mod;
printf("%I64d\n", ans);
}
return 0;
}