Kozak Vus and Colors#10488
Cossack Vus recently discovered stones lined up in a row. He also has different paints, each uniquely numbered from to .
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.
The first line contains two integers and (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 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 a single integer — the number of ways to paint the stones, calculated modulo 10^9+7.
Example 1
Example 2
Example 3
( points): n, k \le 7;
( points): n, k \le 200, a_i=0;
( points): n, k \le 200;
( points): n, k \le 3000;
( points): no additional constraints.