#!/bin/python3

import sys

def countArray(n, k, x):
    one_count = 1
    other_count = 0
    sum_ways = 1
    modulus = 1000000007
    for i in range (n-1):
        one_count = (sum_ways - one_count)%modulus;
        other_count = (sum_ways - other_count)%modulus
        sum_ways = ((k-1)*other_count + one_count)%modulus
    if x == 1:
        return one_count
    else:
        return other_count
        

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)