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

Constraints

\(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

5

Sample Explanation

There are \(5\) possible original arrays:
\((1,2,3,1,2,1,2)\)
\((1,2,3,1,2,3,2)\)
\((1,2,3,1,3,1,2)\)
\((1,2,3,2,1,3,2)\)
\((1,2,3,2,3,1,2)\)









Contact Us
lexmathcsclub@gmail.com
LIT Discord Server