long countArray(int n, long k, int x) {
    int mod = 1000000007;
    long X = k-1, Y = k-2, sum = ((k-1) * (k-1)) % mod;
    for (int i=2; i <= n-3; i++) {
        X = (sum - X) % mod;
        Y = (sum - Y) % mod;
        sum = (X + Y*(k-1)) % mod;
    }
    if (x == 1) return (sum - X + mod) % mod;
    else return (sum - Y + mod) % mod;
}