#P18049. Mystique as Iris
Mystique as Iris
Mystique as Iris
对于一个由正整数构成的序列,可以执行以下操作:
- 选择序列中两个相邻元素,将其中一个减去 ,将另一个变为 。
- 删除序列中的所有 ,其余元素按原有相对顺序组成新序列。
若一个序列可以经过有限次上述操作变成空序列,则称其为神秘序列。允许执行零次操作。
给定长度为 的数组 和正整数 。数组中的每个元素或者是 内的整数,或者是 。你需要把每个 独立替换为 内的任意整数。
求替换后可以得到多少个不同的神秘序列,答案对 取模。
只统计最终数组的不同取值方案;同一个数组即使有多种消除顺序,也只计一次。
输入格式
第一行两个整数 。
第二行 个整数 。
输出格式
输出一行一个整数,表示答案对 取模的结果。
数据范围
,。每个 均满足 或 。
样例 1
输入:
2 2
-1 -1
输出:
3
样例 2
输入:
6 10
-1 -1 -1 -1 1 7
输出:
9125