Nimbus, techfest of NIT Hamipur is going on and Team.exe (departmental team of CSE) is organizing an event called codeswap. Codeswap is a team event containing 3 members in a team.

Now, one of the 3 members of the team is given a number D and the other member is given a number R. Now, the third member is given a number N such that (N-R) % D = 0.

You are given the numbers N, D and R and you have to find the number of permutations of N such that the equation

(N-R) % D = 0 is satisfied. It is possible that there exist zero permutations of N which satisfies the above equation.

NOTE- if N=3009 then 0093 (containing leading zeros) is a valid permutation of N.

INPUT

The input contains 3 integers N, D, R, denoting variables as mentioned in the problem statement.

OUTPUT

The output should contain a single integer with a newline character at end.

CONSTRAINTS

0 ≤ N ≤ 10^14

1 ≤ D ≤ 1000

0 ≤ R ≤ D-1