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 the

three given integers.

Constraints

$2N{10}^9$

$3M{10}^9$

$0K$min$(50,N-1)$

Sample Test Cases

Case $1$ input $230$ output $7$

case $2$ input $231$

output $2$

case $3$ input $5102$

output $1368$