题目描述

当危机四伏，人们常常通过密信来传递求救信息。

在很多很多年以后，历史学家小 Z 翻阅古籍发现了一些模糊的密信，这些密信其中一些文字已经难以辨认，但在可以辨认的文字中，小 Z 发现了他记忆中的符号 "SOS"，这是国际通用的求救信号。小Z 深 知这个信号的重要性，他想知道原始的密信上有多少种可能会出现三次及以上 "SOS" 的组合方式。

小 Z 知道，这些密信可能隐藏着无数种解读方式，但他只关心那些包含三次及以上 "SOS" 的组合（注意 "SOSOS" 只能算出现一次）。

他希望通过计算这些组合的数量，来更深入地了解这些密信背后的故事和含义，这样的合法的密信可能有很多，小 Z 只想知道这些合法组合对 1e9+7 取模的结果即可。

输入格式

第一行输入的是整数 $n$ 表示一封密信的长度，请注意密信只可能包含大写的英文字母 。

输出格式

一个数字，表示有多少种字符串可能出现了三个及以上SOS。

输入输出样例 #1

输入 #1

10

输出 #1

104

输入输出样例 #2

输入 #2

174

输出 #2

122889315

输入输出样例 #3

输入 #3

17711

输出 #3

665739088

输入输出样例 #4

输入 #4

308235

输出 #4

701079308

说明/提示

说明/提示

样例 1 解释

解释：SOSSOSSOS* $26$ 种，*SOSSOSSOS $26$ 种，SOSSOS*SOS $26$ 种，SOS*SOSSOS $26$ 种，其中 * 表示通配符，表示该位置可以放任意 A $-$ Z 的大写字母。

数据范围

对于 $20\%$ 的数据，$n \le 13$

对于 $40\%$，$n \le 200$

对于 $60\%$，$n\le 10^5$

对于 $100\%$，$n \le 10^6$