该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

对于一个长度不超过 $n$，且包含子序列 "sd" 并只由小写英文字母构成的字符串有多少个？由于答案可能很大，你只需要输出答案对 $10^9+7$ 取模的结果。

所谓字符串的子序列，指一个字符串删除部分字符（也可以不删除）得倒的字符串。例如，"abcd" 的子序列可以是 "ab", "ac" 等，但不能是 "adc"。

输入格式

输入一行一个整数 $n$。

输出格式

输出一行一个整数，表示满足条件的字符串数量对 $10^9+7$ 取模的结果。

样例

输入数据 1

2

输出数据 1

1

输入数据 2

3

输出数据 2

77

输入数据 3

874520

输出数据 3

16471619

说明提示

样例 1 解释

只有 "sd" 一个字符串合法。

样例 2 解释

长度为 $3$ 的字符串中：

• 形状是 "s?d" 的共有 $26$ 个。
• 形状是 "?sd" 的共有 $26$ 个。
• 形状是 "sd?" 的共有 $26$ 个。

其中，"ssd" 和 "sdd" 被多算了一次，所有共有 $3*26-2=76$ 个，再加上长度为 $2$ 的一个，总共长度不超过 $3$ 的合法的字符串共有 $77$ 个。

数据范围

$2\le n \le 10^6$。