Problem Brief

To Good Arrays

You are given three integers N, M and K.

An array is said to be good if there is exactly K indices i such that A[i] * A[i + 1] is equal to M.

Find the number of good arrays A. Since the answer can be very large, return it modulo 10^9 + 7.

Input Format

The first line contains an integer, N, denoting one of the given three integers.

The next line contains an integer, M, denoting one of the three given integers.

The next line contains an integer, K, denoting one of the three given integers.

1Example 1

Input

N = 2, M = 3, K = 0

Output

Explanation

Given N = 2, M = 3, K = 0.

There exists 7 possible arrays A. Some of them are [3, 3] and [1, 2].

Input

N = 2, M = 3, K = 1

Output

Explanation

Given N = 2, M = 3, K = 1.

There exists only two possible arrays A which are [1, 3] and [3, 1].

Input

N = 5, M = 10, K = 2

Output

1368

Explanation

Given N = 5, M = 10, K = 2.

There exists a total of 1368 possible arrays A.

Limits and guarantees your solution can rely on.

2 <= N <= 10^9
3 <= M <= 10^9
0 <= K <= min(50, N - 1)