1446. 字符串计数

给定一个长度为 mm 且仅由大写英文字母组成的字符串 aa,请问有多少个长度为 nn 的字符串 bb 满足:

  • aabb 的子串
  • bb 仅由大写英文字母组成

答案对 109+710^9+7 取模。

输入

第一行一个整数 n (1n1000)n \ (1 \leq n \leq 1000)

第二行一个仅由大写英文字母组成且长度为 m (1m100)m \ (1 \leq m \leq 100) 的字符串 aa

输出

一个整数,表示答案。

样例

标准输入 复制文本
6
ABCDB
标准输出 复制文本
52

提示

bbaa 的子串当且仅当删除 aa 开头和末尾连续若干个(可以是 0 个)字符可以得到 bb

样例中满足题意的字符串都符合 xxABCDB 或 ABCDBxx 的形式,其中 xx 可以是 A-Z 二十六个字母中的一个,所以一共 26×226×2 种字符串。

登录以提交代码。
单点时限 1 秒
内存限制 256 MB
提交 97
通过 13