题目内容

窑作坊要在一条釉下彩纹带上点样。纹带被分成 $m$ 格，每一格必须涂成一个小写字母釉色（共 26 种，即 a 到 z）。工规写明：同一釉色不能连续占据超过 3 格。也就是说，出现连续 4 个相同字母（例如 dddd）的纹带作废；像 dddeddd 这种中间被打断的则仍算合格。

给定纹带长度 $m$，请统计有多少种合格涂法。答案可能很大，对 1000000007 取模后输出。

约束：

• 1 $\le$ $q$ $\le$ 200000
• 1 $\le$ $m$ $\le$ 200000

输入描述

第一行一个整数 $q$（1 $\le$ $q$ $\le$ 200000），表示随后有多少条询问。

接下来 $q$ 行，每行一个整数 $m$（1 $\le$ $m$ $\le$ 200000），表示该条询问的纹带长度。

输出描述

输出 $q$ 行，每行一个整数，表示对应长度的合格涂法数对 1000000007 取模后的结果。

样例1

输入

3
1
3
5

输出

26
17576
11880050

说明

• $m=`1`$：一格可涂 26 种釉色，都合格。
• $m=`3`$：长度不到 4，不可能出现四连，方案数为 $26^3=`17576`$。
• $m=`5`$：需要扣掉含四连的涂法，合格数为 11880050。

样例2

输入

2
6
8

输出

308864400
769484794

说明

两条询问分别对应长度 6 与 8 的纹带，均已对 1000000007 取模。

样例3

输入

1
7

输出

30034944

说明

长度 7 的合格涂法对 1000000007 取模后为 30034944。