Construct the Array

• Time : O(n)
• Space : O(1)

long countArray(int n, int k, int x) {
    long long xdp = x == 1 ? 1 : 0, ydp = x == 1 ? 0 : 1;
    long long mod = 1e9 + 7;
    for(int i = 1; i < n; i++) {
        long long nxdp = ydp;
        long long nydp = (ydp * (k - 2) % mod + xdp * (k - 1) % mod) % mod;
        xdp = nxdp;
        ydp = nydp;
    }
    return xdp;
}