Let's keep the problem statement easy, shall we?
How many integers of length N are such that sum of square of digits in exactly K and they are divisible by M?

Input Format

First line contains three space separated integers : N , M and K.

Output Format

Output the only integer as described in the question. Since the answer can be too big, output it modulo 10^9 + 7.

Constraints

**1 ≤ N ≤ 50

1 ≤ M ≤ 100

1 ≤ K ≤ 2000**

SAMPLE INPUT
2 12 20

SAMPLE OUTPUT
1

Explanation

The only number that satisfies is 24.

见题面

见题面