[登峰造极-2016]_QAQ字符串

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

SDUTACM集训队在2016年第41届ACM-ICPC国际大学生程序设计竞赛亚洲区域赛青岛赛站获得金奖1项,实现了山东理工大学金牌零的突破;在首届中国高校计算机竞赛团体程序设计天梯赛中以全国总决赛第6名的成绩获得高校一等奖。

 

以QAQ名字命名的字符串被称为QAQ字符串。

现在QAQ想知道至少含有一个QAQ连续子串的长度为n的字符串有多少个(字符集为大写字母)?
例如 n = 3 时只有 "QAQ" 1个, n = 4 的时候有 "QAQA", "QAQB" ... "QAQZ", "ZQAQ", "YQAQ" ... "AQAQ" 52 个。

答案可能很大,请将答案对1e9+7取模。

Input

多组输入,组数不超过200。

每行输入一个整数n 。

( 1 <= n <= 1e5)

Output

输出一行,包含一个整数即为答案。

Sample Input

3

Sample Output

1

Hint

Source

【重聚--SDUTACM十周年庆典专场赛】Fish