Migrated from Lutece 3272 无抬头-

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tags: KMP，容斥，计数 DP，Periodicity Lemma

“声音的本质是机械波，是物质的震动。

“而机械波又可分为横波和纵波，由于空气只能传播纵波，所以我们能够听到的声音都是纵波

“在知道声音的本质后，经过反复尝试，人们便学会了如何记录声音。最早的留声机就像这样——把胶片放上去——说实话这玩意还挺贵的，但总是还有像我这样的‘发烧友’会买呢，哈哈。

“这种古董的原理并不复杂，只需要在录制声音时，使用一个随声音震动的针头在胶片上记录下声音的强弱；播放时，让针头按照胶片上的轨迹震动，便可还原。后来使用磁粉替代了胶片，磁带便由此而生。

“此外，在一端将声音的强弱转化为电流的强弱，又在另一端将电流重新转化为声音，这样就可以使用电流来传递我们的声音；后来我们又用空间中的电磁波去替代导体中的电流，可以让声音传播得更远。

“刚才说的都是模拟信号的方法，模拟信号虽然还原度高，但是很容易受噪音干扰。为了减小声音在传播和复现中的损失，人们又发明了数字储存声音的方式。

“具体来说，声音的强弱可以转化为一系列离散的强弱值，虽然从连续到离散的过程中意味着损失，但是只要采样的频率足够高，采样时取值足够多，那么离散的信号就与原信号就越接近。——对于绝大多数人而言，是听不出差别的。

“但是无论是胶片还是磁带，还是数字储存的音频信号，在几万年后，都会逐渐失真，变成我们听不懂的噪音……”

“说的真好——那我问问你，几万年后，当你再次播放这个胶片时，你还能听得出我的声音吗？”

---

令字符集 $\Sigma=\lbrace1, 2, \dots, m\rbrace$ 下有两个字符串 $S$ 和 $T$，$|S|=n$, $|T|=l$，其中 $T$ 已知，$S$ 中的每一个字符都服从于 $[1, m]$ 上的离散均匀分布且字符间的取值两两相互独立。求 $T$ 在 $S$ 中至少出现一次的概率是多少。

这是个悲伤的数字，你只需要输出这一概率对 $1000000007\scriptsize{\ =10^9+7}$ 取模后的结果即可。

Input

第一行包含三个整数 $n, m, l$，含义如上文所述。

第二行包含 $l$ 个整数，表示字符串 $T$。（请注意，这里字符串中的元素是正整数而非字符）

Output

输出一行一个整数，表示 $T$ 至少在 $S$ 中出现一次的概率在 $1000000007$ 模意义下的结果。

Samples

3 2 2
1 2

500000004

10 5 5
1 2 5 5 3

114011444

1100005 2 5
1 2 2 1 2

279814323

Constraints

$1\le l\le 1.1 \times 10^6$ 且 $\ l\le n\le l+1.1\times10^6$

$1\le m\le 10^9$

保证出现在 $T$ 中的所有元素均在 $1$ 到 $m$ 之间。

Resources

2024 UESTC ICPC Training for String