题目描述

小新是一个字符串达人，他喜欢一些满足特殊要求的字符串，国庆节到了，现在只要这个字符串子序列包含 "cn"他就喜欢。小新想让你求解长度在 $n$ 以内，能让小新喜欢的字符串有多少个？答案对 $10^9+7$ 取模。

输入格式

一个正整数$n(2\leq n \leq 10^6)$

输出格式

一个正整数，表示合法字符串数量对$10^9+7$取模的值。

样例

2

1

3

77

提示

对于样例1：仅有“cn”一个字符串合法。

对于样例2：“?cn","c?n","cn?"各有26个，但是"cnn"和"ccn"重复计算，减去。再加上长度为2的"cn"，答案为$3 \times 26 - 2 + 1 = 77。$