long long countArray(int n, int k, int x) {
    long long MOD = 1000000007;

    // dp[i][j] = number of arrays of length i+1 ending with j
    // (Note: i is 0-indexed for length here, so dp[i] is for length i+1)
    std::vector<std::vector<long long>> dp(n, std::vector<long long>(k + 1, 0));

    // Base case: Array of length 1 (i=0)
    // The first element is fixed to 1.
    dp[0][1] = 1;

    for (int i = 1; i < n; ++i) { // Iterating through lengths (from 2 to n)
        long long sum_prev_row = 0;
        // Calculate sum of ways for previous length (length i)
        for (int prev_val = 1; prev_val <= k; ++prev_val) {
            sum_prev_row = (sum_prev_row + dp[i-1][prev_val]) % MOD;
        }

        for (int current_val = 1; current_val <= k; ++current_val) {
            // Number of ways to end with current_val is total ways from previous length
            // MINUS ways where previous_val was also current_val.
            dp[i][current_val] = (sum_prev_row - dp[i-1][current_val] + MOD) % MOD;
        }
    }

    return dp[n-1][x];
}

long long countArray(int n, int k, int x) {
    long long MOD = 1000000007;

    // prev[j] stores ways to form array of length 'current_length - 1' ending with 'j'
    std::vector<long long> prev(k + 1, 0);
    
    // Base case: Array of length 1
    prev[1] = 1; 

    // prev_sum holds the total number of ways for the previous length
    long long prev_sum = 1; // Initially, only prev[1] is 1

    for (int i = 1; i < n; ++i) { // i represents current length - 1 (looping for lengths 2 to n)
        std::vector<long long> curr(k + 1, 0); // For the current length (i+1)
        long long current_sum = 0; 

        for (int a = 1; a <= k; ++a) {
            // To form an array of length (i+1) ending with 'a':
            // Sum of all ways for length 'i' (prev_sum)
            // Minus ways where the previous element was also 'a' (prev[a])
            curr[a] = (prev_sum - prev[a] + MOD) % MOD; 
            current_sum = (current_sum + curr[a]) % MOD;
        }
        prev_sum = current_sum; // Update total sum for the next iteration
        prev = curr;            // 'curr' becomes 'prev' for the next length
    }

    // After the loop, 'prev' (which was 'curr' in the last iteration)
    // contains the counts for arrays of length 'n'.
    return prev[x];
}

long long countArray(int n, int k, int x) {
    long long MOD = 1000000007;

    // Handle base case where array length is 1
    if (n == 1) {
        return (x == 1) ? 1 : 0;
    }

    // dp_ends_with_1: Number of ways to form an array of length 'i' ending with 1
    long long dp_ends_with_1 = 0; 
    // dp_ends_with_other: Number of ways to form an array of length 'i' ending with a value != 1
    long long dp_ends_with_other = 0;

    // Initialize for arrays of length 1
    // The first element must be 1.
    dp_ends_with_1 = 1; // Array: [1]
    dp_ends_with_other = 0; // No way to end with other value if length is 1 and starts with 1

    // Iterate for lengths from 2 to n
    for (int i = 2; i <= n; ++i) {
        long long next_dp_ends_with_1;
        long long next_dp_ends_with_other;

        // To form an array of length 'i' ending with 1:
        // The previous element (at length i-1) must not be 1.
        // So, it comes from dp_ends_with_other.
        next_dp_ends_with_1 = dp_ends_with_other;
        
        // To form an array of length 'i' ending with a value j (where j != 1):
        // Case 1: Previous element was 1 (dp_ends_with_1 ways).
        // From these, we can choose any of the (k-1) values that are not 1.
        long long from_prev_1 = (dp_ends_with_1 * (k - 1)) % MOD;

        // Case 2: Previous element was some p (where p != 1) (dp_ends_with_other ways).
        // From these, we can choose any of the (k-2) non-1 values that are also not p.
        long long from_prev_other = (dp_ends_with_other * (k - 2)) % MOD;

        next_dp_ends_with_other = (from_prev_1 + from_prev_other) % MOD;

        // Update current states for the next iteration
        dp_ends_with_1 = next_dp_ends_with_1;
        dp_ends_with_other = next_dp_ends_with_other;
    }

    // After the loop, dp_ends_with_1 and dp_ends_with_other hold counts for length n.
    if (x == 1) {
        return dp_ends_with_1;
    } else {
        return dp_ends_with_other;
    }
}

NUM = 10**9+7

def countArray(n, k, x):
    dp = [[0 for _ in range(2)] for _ in range(n+1)]
    
    # dp[length][ends in x]
    
    dp[2][0] = k - 2 if x != 1 else k - 1
    dp[2][1] = 1 if x != 1 else 0
    
    for i in range(3, n+1):
        dp[i][0] = ((((k-2) % NUM) * (dp[i-1][0] % NUM)) % NUM + (((k-1) % NUM) * (dp[i-1][1] % NUM)) % NUM) % NUM
        dp[i][1] = dp[i-1][0] % NUM
    
    return dp[n][1] % NUM

function countArray(n: number, k: number, x: number): number {
    // Return the number of ways to fill in the array.
    //ending in number col+1
    //array of length row+2
    //NOTE: for EVEN length, there is one less array ending in 1. for ODD, there is one extra.
    // Otherwise, the number of constructable arrays of length n ending in k is equal to the sum of all arrays of length n-1, + or - one depending on n's parity.
    let curr = 1;
    
    let mod = (Math.pow(10,9)+7)
    
    let even;
    let odd;
    //iterate over possible lengths
    for(let i=2; i<n; i++)
    {
        even = i%2
        odd = even==1?0:1
        //add even bonus, remove odd
        curr = (curr*(k-1) + even - odd) % mod
    }
    if(x==1) curr += (-even + odd)
    
    return curr
}