题目内容

灯具车间要给一批展台灯带排产。值班员需要按长度统计合法染色方案，好把数量写入当晚的工艺单。

每条灯带有 $k$ 格，每格必须涂成 26 种色号中的一种。车间规程禁止出现连续四格同色：像四连相同色号就不合格，但「三连相同再换色、后面再出现三连」仍然合格。

现在给出若干条灯带的长度，请分别算出每种长度有多少种合法染色。方案数可能很大，输出时对 1000000007 取模。

询问条数 $q$ 满足 $1 \le q \le$ 200000，每条灯带长度 $k$ 满足 $1 \le k \le$ 200000。

输入描述

第一行一个整数 $q$（$1 \le q \le$ 200000），表示随后有多少条待统计的灯带。

接下来 $q$ 行，每行一个整数 $k$（$1 \le k \le$ 200000），表示一条灯带的格数。

输出描述

输出 $q$ 行，每行一个整数，即对应长度的合法染色方案数对 1000000007 取模后的结果。

样例1

输入

3
1
3
5

输出

26
17576
11880050

说明

• $k=1$：一格可任选 26 种色号。
• $k=3$：最长也只能连三格，全部 $26^3=17576$ 种都合法。
• $k=5$：在长度 4 的 $26^4-26$ 种合法前缀上继续染色，按「当前结尾连续同色格数不超过 3」递推，得到 11880050。

样例2

输入

1
6

输出

308864400

说明

长度为 6 时，继续在上一长度的合法方案上扩一格：可以换色另起一连，或把结尾的一连、两连同色再延长一格，但不能把已经三连的再涂成四连。