字符串
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

给你一个整数 n 。
如果一个字符串 s 只包含小写英文字母,且 将 s 的字符重新排列后,新字符串包含 子字符串 "leet" ,那么我们称字符串 s 是一个 好 字符串。
比方说:

字符串 "lteer" 是好字符串,因为重新排列后可以得到 "leetr" 。
"letl" 不是好字符串,因为无法重新排列并得到子字符串 "leet" 。
请你输出长度为 n 的好字符串 总 数目。

由于答案可能很大,将答案对 10^9 + 7取余 后返回。

子字符串 是一个字符串中一段连续的字符序列。

输入描述:

个整数 n

输出描述:

长度为 n 的好字符串  数目
示例1

输入

复制
4

输出

复制
12
示例2

输入

复制
10

输出

复制
83943898

备注:

1\le n \le 10^5