Fill The Gaps

# D. Fill The Gaps

#### 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$$.

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

7 3
1 0 3 0 0 0 2

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)$$ lexmathcsclub@gmail.com LIT Discord Server