111_D. Petya and Coloring_5143
Little Petya loves counting. He wants to count the number of ways to paint a rectangular checkered board of size n × m (n rows, m columns) in k colors. Besides, the coloring should have the following property: for any vertical line that passes along the grid lines and divides the board in two non-empty parts the number of distinct colors in both these parts should be the same. Help Petya to count these colorings.

Input

The first line contains space-separated integers n, m and k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 106) — the board's vertical and horizontal sizes and the number of colors respectively.

Output

Print the answer to the problem. As the answer can be quite a large number, you should print it modulo 109 + 7 (1000000007).

Examples

Input

2 2 1


Output

1


Input

2 2 2


Output

8


Input

3 2 2


Output

40
//package practice;

import java.util.Scanner;

/**
 * Created by yi on 2015/10/29.
 */
public class Coloring {
    public static int mod = 1000000007;
    static long fac[];
    static long rev[];
    static long dp[];

    static long pow_mod(long a, int i, long n) {
        if (i == 0) return 1 % n;
        long temp = pow_mod(a, i >> 1, n);
        temp = temp * temp % n;
        if ((i & 1) == 1) temp = temp * a % n;
        return temp;

    }

    static void init() {
        fac = new long[1000005];
        rev = new long[1000005];
        dp = new long[1005];
        fac[0] = 1;
        fac[1] = 1;
        rev[0] = 1;
        for (int i = 1; i <= 1000000; i++) {
            fac[i] = fac[i - 1] * i % mod;
        rev[i] = pow_mod(fac[i], mod - 2, mod);
        }
    }

    static long C(int n, int m) {
        return (fac[n] * rev[m] % mod) * rev[n - m] % mod;
    }

    public static void main(String[] args) {
        init();
        int n, m, k;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        k = scanner.nextInt();
        if (m == 1) {
            System.out.println(pow_mod(k, n, mod));
            return;
        }

        for (int i = 1; i <= n && i <= k; i++) {
            dp[i] = pow_mod(i, n, mod);
            for (int j = 1; j < i; j++) {
                dp[i] = (dp[i] - C(i, j) * dp[j] % mod) + mod;
                dp[i] %= mod;
            }
        }

        long ans = 0;
        if (m == 2) {
            for (int i = 1; i <= n && i <= k; i++) {
                ans = (ans + (((dp[i] * dp[i] % mod) * C(k, i) % mod) * C(k, i)) % mod) % mod;
            }
            System.out.println(ans);
        } else {
            for (int i = 1; i <= n && i <= k; i++) {
                for (int j = 0; 2 * j + i <= k && i + j <= n; j++) {
                    long tmp = dp[i + j] * dp[i + j] % mod;
                    tmp = ((tmp * C(k, i) % mod) * C(k - i, j) % mod) * C(k - i - j, j) % mod;
//                    System.out.println(""+k+" "+i+" "+C(k,i));
                    tmp = (tmp * pow_mod(i, n * (m - 2), mod)) % mod;
                    ans = (ans + tmp) % mod;
                }
            }
            System.out.println(ans);
        }
    }

}
