const long divide = pow(10, 9) + 7;

    // Return the number of ways to fill in the array.
long countArray(int n, int k, int x) 
{
    if (n == 3)
    {
        if (x == 1)
            return long(k-1)%divide;
        else
            return long(k-2)%divide;   
    }
    else
    {
				// Array of answers for various n and x=1
        vector<long> A;
				// Array of answers for various n and x!=1 (does not depend on specifica value of x)
        vector<long>B;
        
        A.reserve(n-2);
        B.reserve(n-2);
        
				// special case n=3
        A.push_back((k-1)%divide);
        B.push_back((k-2)%divide);
        
				// increase n by 1 recurrently
        for(int i = 0 ; i < n-3 ; i++)
        {
            long a = (k-1)*B.back();
            long b = A.back() + (k-2)*B.back();
            a = a % divide;
            b = b % divide;
            A.push_back(a);
            B.push_back(b);
        }
        if(x == 1)
            return A.back();
        else
            return B.back();
    }

}