Niko 有一个长度为 的整数序列 以及两个整数 ，保证 。
求有多少种将 中的 替换为 中的整数的方式，使得 中不存在长度为 的连续相同区间。答案对 取模。
第一行三个正整数 。
第二行 个整数 。
输出一行一个数，表示合法的方案数对 取模的结果。
5 2 3 1 -1 1 -1 2
2
6 3 2 1 1 -1 -1 -1 -1
0
10 42 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
989891925
对于所有数据，，，，输入均为整数。
