Required Substring

题目描述

你的任务是计算长度为 n 的字符串中包含给定长度为 m 的模式作为子串的字符串数量。所有字符串由字符 A–Z 组成。

输入格式

第一行输入是一个整数 n：最终字符串的长度。 第二行是一个长度为 m 的模式。

输出格式

输出字符串数量对 $10^9+7$ 取模的结果。

6
ABCDB

52

提示

$1 \le n \le 1000$ $1 \le m \le 100$ 样例解释：最终字符串的形式将是 ABCDBx 或 xABCDB，其中 x 是任意一个 A–Z 之间的字符。

标签: CSES1112|字符串

来源

CSES1112|字符串