Expert.
Put your skills to the test.

Problem summary

Color a row of N stones with colors 1 through K. Some colors are fixed and zeros are uncolored. Count completions with distinct colors on adjacent stones, modulo 1000000007.

Constraints

1 ≤ N ≤ 500000; 3 ≤ K ≤ 10^9. Adjacent fixed stones never already have equal colors.

Worked example

Official example, transcribed with whitespace restored from the PDF.

4 3
2 0 1 0

2

Solution analysis

1. Split the row at its fixed stones. A free prefix or suffix of length L next to a fixed stone contributes (K−1)^L; if there are no fixed stones the answer is K(K−1)^(N−1). The internal gaps are independent once their endpoints are fixed.
2. For an internal gap, anchor its left endpoint color. Let same[d] count walks of d color changes returning to that color, and different[d] count walks ending at one particular different color. Initially these are 1 and 0. Their recurrences are same[d+1]=(K−1)different[d] and different[d+1]=same[d]+(K−2)different[d].
3. For fixed positions distance d apart, multiply by same[d] if their colors agree and different[d] otherwise. In the sample, between colors 2 and 1 only color 3 is possible, while the final stone has two choices.

Why it works

The two recurrence states partition the possible preceding color into the anchor color and the K−1 symmetric other colors. They therefore count each proper color walk exactly once. Given fixed endpoints, disjoint gaps impose no further shared choices, so multiplying their counts and the free-end factors counts exactly all completions.

Watch out. Different counts completions for one specified endpoint color, not all non-anchor colors.

An independently written complete program with standard headers.

// Key idea: The two recurrence states partition the possible preceding color into the anchor color and
// the K−1 symmetric other colors. They therefore count each proper color walk exactly once.
#include<iostream>
#include<vector>
using namespace std;
const long long MOD=1000000007;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long k;
    cin>>n>>k;
    vector<long long>same(n+1),diff(n+1),power(n+1);
    same[0]=power[0]=1;
    for(int d=1;d<=n;++d){
        same[d]=(k-1)*diff[d-1]%MOD;
        diff[d]=(same[d-1]+(k-2)*diff[d-1])%MOD;
        power[d]=power[d-1]*(k-1)%MOD;
    }
    int previous=-1;
    long long color=0,answer=1;
    for(int i=0;i<n;++i){
        long long x;
        cin>>x;
        if(x==0){
            continue;
        }
        if(previous==-1){
            answer=power[i];
        }
        else{
            answer=answer*(x==color?same[i-previous]:diff[i-previous])%MOD;
        }
        previous=i;
        color=x;
    }
    if(previous==-1){
        answer=k*power[n-1]%MOD;
    }
    else{
        answer=answer*power[n-1-previous]%MOD;
    }
    cout<<answer<<'\n';
}