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