G. 所需子串

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

翻译自 CSES-1112 题。

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

第一行包含一个整数 $n$ ，表示最终字符串的长度。

第二行包含一个模式字符串，长度为 $m$ 。

输出包含给定模式字符串作为子串的字符串数量，结果对 $10^9+7$ 取模。

6
ABCDB

最终字符串将是类似 ABCDBx 或 xABCDB 的形式，其中 x 代表 $A–Z$ 之间的任意字符。

$1 \leq n \leq 1000$ ；

$1 \leq m \leq 100$ 。