CF535D Tavas and Malekas
题目描述
Tavas 是一个非常奇怪的生物。通常人在睡觉时嘴里会发出 “zzz” 的声音，而 Tavas 睡觉时嘴里却会说出一个长度为 $n$ 的字符串 $s$。
今天 Tavas 在 Malekas 的家里睡着了。趁他睡着时，Malekas 对 $s$ 做了一些操作。Malekas 有一个自己喜欢的字符串 $p$。他决定找出所有满足 $p$ 在 $s$ 中匹配的位置 $x_{1}
输入格式
第一行包含两个整数 $n$ 和 $m$，分别表示 $s$ 的长度和 Malekas 写下的子序列的长度（$1 \leq n \leq 10^6$，$0 \leq m \leq n - |p| + 1$）。
第二行包含字符串 $p$（$1 \leq |p| \leq n$）。
第三行包含 $m$ 个空格分隔的整数 $y_{1}, y_{2}, ..., y_{m}$，即 Malekas 写下的子序列（$1 \leq y_{1} < y_{2} < ... < y_{m} \leq n - |p| + 1$）。
输出格式
输出一行，表示可能的 $s$ 的数量，对 $1000000007$ 取模。
说明/提示
在第一个样例中，所有形如 "ioioi?" 的字符串都满足条件，其中问号代表任意一个英文字母。
这里 $|x|$ 表示字符串 $x$ 的长度。
请注意，存在没有合法字符串 $s$ 的情况（此时答案为 0）。
由 ChatGPT 5 翻译