长度不超过nn，且包含子序列“us”的、只由小写字母构成的字符串有多少个？ 答案对10^9+710
9 +7取模。
所谓子序列，指一个字符串删除部分字符（也可以不删）得到的字符串。
例如，“unoacscc"包含子序列"us”，但"scscucu"则不包含子序列"us"
输入描述： 一个正整数n
输出描述： 一个正整数，为满足条件的字符串数量对10^9+7取模的值
此题只要能够写出状态转移方程就比较好写了
如果没有及时取余的话会导致超时
所以要在每次迭代的时候就及时做取余操作
状态中有三个参数：
f
[
n
]
=
[
d
p
1
,
d
p
2
,
d
p
3
]
f[n] = [dp_1,dp_2,dp_3]
f[n]=[dp1,dp2,dp3]
- d p 1 dp_1 dp1表示n位数字时，完全不含有u和s的字符串个数
- d p 2 dp_2 dp2表示n位数字时，含有u但是不含有前u后s的字符串个数
- d p 3 dp_3 dp3表示n位数字时，已经含有前u后s的字符串个数
转移公式如下表示：
d
p
3
=
d
p
2
+
d
p
3
∗
26
dp_3 = dp_2 + dp_3*26
dp3=dp2+dp3∗26
d
p
2
=
d
p
1
∗
25
+
d
p
2
dp_2 = dp_1*25 + dp_2
dp2=dp1∗25+dp2
d
p
1
=
d
p
1
∗
25
dp_1 = dp_1*25
dp1=dp1∗25
用时和内存都排名很前面：
n = int(input())
def dfs(n):
if n == 2:return 1
dp = [25,1,0]#无u,有u无us，有us
result = 0
mod = 10**9+7
for i in range(2,n+1):
dp[2] = (dp[1]+dp[2]*26)%mod
dp[1] = (dp[0]+dp[1]*25)%mod
dp[0] = (dp[0]*25)%mod
result += dp[2]
return result%mod
print(dfs(n))
