3005. 设计密码
时间限制：1000 MS 内存限制：64 MB
题目描述
## 题目描述 你现在需要设计一个密码 $S，S$ 需要满足： - $S$ 的长度是 $N$； - $S$ 只包含小写英文字母； - $S$ 不包含子串 $T$； 例如：$abc$ 和 $abcde$ 是 $abcde$ 的子串，$abd$ 不是 $abcde$ 的子串。 请问共有多少种不同的密码满足要求？ 由于答案会非常大，请输出答案模 $10^9+7$ 的余数。 ## 输入格式 第一行输入整数$N$，表示密码的长度。 第二行输入字符串$T，T$中只包含小写字母。 ## 输出格式 输出一个**正整数**，表示总方案数模 $10^9+7$后的结果。 ## 输入 ```in1 2 a ``` ## 输出 ```out1 625 ``` ```in2 4 cbc ``` ```out2 456924 ``` ## 提示