题目描述

愚蠢的小明觉得自己喜欢的条件太苛刻了，很难找到合适的字符串，现在对于某个字符串，只要这个字符串子序列包含 $“cn”$ 的他就喜欢。

小明想让你求解长度在 $n$ 以内，能让小明喜欢的字符串有多少个？ 答案对 $10^9+7$ 取模。

输入描述

一个正整数$n（2 \leq n \leq 10^6）$

输出描述

一个正整数，为满足条件的字符串数量对 $10^9+7$ 取模的值

输入输出样例

2

1

说明

仅有“cn”这一个字符串合法

3

77

样例2说明

在长度为3的字符串里，

"c?n"有26个

"?cn"有26个

"cn?"有26个。

但是,"cnn"和"ccn"都重复计算量一次，应该减去，

所以长度为3的字符串符合要求的共有26*3-2=76个。

再加上长度为2的"cn"，所以长度不超过3且达到要求的字符串共有77个。

对于测试点1，$n<=5$

对于测试点2，$n<=10$

对于测试点3，$n <= 100$