import java.util.Scanner;

public class ProblemB3 {
    private static final long B = 1000000007;

    public ProblemB3() {
        solve();
    }

    private void solve() {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int x = in.nextInt();
        long answer = countArray(n, k, x);
        System.out.println(answer);
        in.close();
    }

    private long mul(long a, long b) {
        return ((a%B)*(b%B))%B;
    }

    private long add(long a, long b) {
        return ((a%B)+(b%B))%B;
    }

    private long sub(long a, long b) {
        return (a+B-(b%B))%B;
    }

    private long countArray(int n, int k, int x) {
        long k1 = sub(k, 1);
        long k2 = sub(k, 2);
        if(n == 3) {
            return x==1?k1:k2;
        }
        if(k == 2) {
            return ((x == 2) ^ (n%2==1))?1:0;
        }
        long u = 0;
        long v = 1;
        for(int i=0;i<n-3;i++) {
            long u2 = mul(v, k1);
            long v2 = add(u, mul(v, k2));
            u = u2;
            v = v2;
        }
        if(x == 1) {
            return mul(v, k1);
        } else {
            return add(u, mul(v, k2));
        }
    }

    public static void main(String[] args) {
        new ProblemB3();
    }
}