题目描述

小蓝，一位昔日的编程大神，如今却因找不到工作，转行成了飞天大盗。近日，他正筹划着盗取蓝桥王国的至宝——水晶项链。

水晶项链被珍藏在一个固若金汤的保险库中，要想开启保险库，就必须破解保险库的密码。利用编程技能，小蓝截获情报，得知这个密码是一个长度为 $N$，且仅由小写英文字母构成的“近似回文字符串”。

一个字符串 $S$ 被称为“近似回文字符串”需满足以下条件：

1. $S$ 本身不是回文串。
2. 从 $S$ 中删除一个字符后，剩下的字符串是回文串。

例如，当 $S = \text{abbac}$ 时，$S$ 不是回文，但删除最后一个字符 $\text{c}$ 后得到的 $\text{abba}$ 是回文，所以 $S$ 是“近似回文字符串”。

现在，请你帮助小蓝计算长度为 $N$ 的“近似回文字符串”的数量，为转行做飞天大盗的小蓝提供助力。由于答案可能很大，你只需给出其对 $10^9 + 7$ 取余后的结果即可。

输入格式

输入一行，包含一个整数 $N$，表示密码字符串的长度。

输出格式

输出一个整数，表示长度为 $N$ 的“近似回文字符串”的数量对 $10^9 + 7$ 取余后的结果。

2

650

提示

【评测用例规模与约定】

对于 10% 的评测用例，$2 \leq N \leq 6$。

对于 100% 的评测用例，$2 \leq N \leq 10^5$。