长度不超过 nnn,且包含子序列 us 的、只由小写字母构成的字符串有多少个? 答案对 109+710^9+7109+7 取模。
us
所谓子序列,指一个字符串删除部分字符(也可以不删)得到的字符串。
例如,unoacscc 包含子序列 us,但 scscucu 则不包含子序列 us。
unoacscc
scscucu
输入
一个正整数 n (1≤n≤106)n \ (1 \leq n \leq 10^6)n (1≤n≤106)。
输出
一个正整数,为满足条件的字符串数量对 109+710^9+7109+7 取模的值。
样例
2
1
提示
当 n=2n=2n=2,仅有 us 这一个字符串合法。
来源
2021 牛客寒假算法基础集训营