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**