The following two steps, on an array consisting of positive integers, are called an operation:
Select any two adjacent elements in , decrease one of them by , and set the other to .
Remove all zeros from .
We call if and only if it can be transformed into an empty sequence after a finite number of operations (possibly zero).
You are given an array consisting of integers, as well as an integer . Each element of is either an integer from to or . Your task is to replace every occurrence of in with any integer from to .
Determine the number of distinct mystic arrays that can be obtained after the replacement. Since the answer can be very large, output it modulo .
输入格式
The first line of the input contains two integers and (, ).
The second line of the input contains integers ( or ).
输出格式
Output a single integer, representing the number of distinct mystic sequences that can be obtained, modulo .
样例
样例输入 1
2 2
-1 -1
样例输出 1
3
样例输入 2
6 10
-1 -1 -1 -1 1 7
样例输出 2
9125
数据范围与提示
In the first test, the array is . By replacing both -s, one possible result is . In this case, we select the two adjacent numbers: decrease the first by and set the second to , obtaining . After removing all zeros, the sequence becomes empty. Hence, is a mystic sequence.
Similarly, if we replace the -s with or with , both sequences can also be reduced to empty. Therefore, the total number of distinct mystic sequences is .
