[登峰造极-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