Kozak Vus and Colors

Cossack Vus recently discovered $n$ stones lined up in a row. He also has $k$ different paints, each uniquely numbered from $1$ to $k$.

His goal is to paint the stones such that no two adjacent stones share the same color. However, some stones have already been painted, and these cannot be repainted.

Cossack Vus wants to know how many different ways he can paint the stones while adhering to these conditions. Since the number of possible ways can be very large, you should provide the result modulo $10^9+7$.

Input

The first line contains two integers $n$ and $k$ ($1\le n\le 5\cdot 10^5,3\le k\le 10^9$) — representing the number of stones and the number of available colors, respectively.

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($0\le a_i\le k$) — indicating the colors of the stones. If $a_i=0$, the stone is not yet painted. If $1\le a_i\le k$, the stone is already painted with the color numbered $a_i$.

Output

Output a single integer — the number of ways to paint the stones, calculated modulo $10^9+7$.

Examples

Scoring

1. ($12$ points): $n,k\le 7$;

2. ($11$ points): $n,k\le 200,a_i=0$;

3. ($23$ points): $n,k\le 200$;

4. ($25$ points): $n,k\le 3000$;

5. ($29$ points): no additional constraints.