#include <bits/stdc++.h>
#define c 1000000007
using namespace std;

unsigned long long int countArray(unsigned long long int n, unsigned long long int k, unsigned long int x) 
{
    if(n == 3)
    {
        if(x == 1)
            return (k-1) % c;
            
        else
            return (k-2) % c;
        
    }
    
    else if(n == 4)
    {
        if(x == 1)
            return (k-1)*(k-2) % c;
        
        else
        {
            k--;
            return (k*k-k+1) % c;           
        }        
    }
    
    else
    {
        if(n % 2 == 0)
        {
            if(x == 1) 
            {
                unsigned long long int ans;
                
                ans = pow(k-1,n-3);
                ans *= k-2;
                
                return ans % c;
            }
            
            else
            {
                return 61; 
            }    
        }
        
        else
        {
            if(x == 1)
                return 31;
        }
    }
    
    return 563;
}

int main()
{
    unsigned long long int n;
    unsigned long long int k;
    unsigned long long int x;
    cin >> n >> k >> x;
    
    unsigned long long int answer = countArray(n, k, x);
    
    cout << answer << endl;
    
    return 0;
}