#!/bin/python3

import sys
from fractions import gcd

mod = 10**9 + 7
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y
    
def invert(k):
    g, x, y = egcd(k, mod)
    return x % mod

def countArray(n, k, x):
    # Return the number of ways to fill in the array.
    if x == 1:
        if n <= 2:
            return 0
        elif k <= 1:
            return 0
        value = k - 1
    else:
        if n <= 1:
            return 0
        elif n == 2:
            return 1
        elif n == 3 and k <= 2:
            return 0
        value = k - 2
    for i in range(4, n + 1):
        value = (pow(k - 1, i - 2, mod) - value) % mod
    return value

if __name__ == "__main__":
    n, k, x = input().strip().split(' ')
    n, k, x = [int(n), int(k), int(x)]
    answer = countArray(n, k, x)
    print(answer)