Fill The Gaps

D. Fill The Gaps

No Submission Yet

Problem Statement

CodeTiger found an array of integers while walking around the LHS Lincoln field. Unfortunately, he erased some of the values with his paws. He only knows that all values were between \(1\) and \(M\) and that no adjacent values were the same. Your job is to find the number of possible original arrays. As that number can be very large, find the answer modulo \(10^9 + 7\).

Additional Notes

Time Limit:
C++: 2.5 seconds
Java, Python: 5 seconds
Memory Limit: 128mb


\(2 \le N, M \le 5 \cdot 10^5\) and \(0 \le a_i \le M\)

Input format

The first line has two integers \(N\) and \(M\) \((2\le N, M \le 5 \cdot 10^5)\).

The second line has the array \(a\) \((0\le a_i \le M)\), where 0 means the value was erased.

Output format

Output a single integer indicating the answer

Sample input:

7 3
1 0 3 0 0 0 2

Sample output


Sample Explanation

There are \(5\) possible original arrays:

Contact Us
LIT Discord Server