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取模。

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

每行输入一个整数n 。

（ 1 <= n <= 1e5）

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

3

1