Migrated from Lutece 1160 LCM and GCD

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Can you calculate how many sequence $a_1, a_2, ..., a_k$ satisfied that gcd($a_1, a_2, ..., a_k$) = $d$ and lcm($a_1, a_2, ..., a_k$) = $n$. All $a_i$ ($1 \leq i \leq k$) are positive integers.

gcd is the greatest common divisor and lcm is the least common multiple.

Two sequences $A$ and $B$ are different if there is at least one $i$ ($1 \leq i \leq k$) that $A_i \neq B_i$.

Input

There is only one line contains three integers $k$ ($2 \leq k \leq 10^9$), $d$ ($1 \leq d \leq 10^9$), $n$ ($1 \leq n \leq 10^9$).

Output

Output one line with the answer mod $10^9+7$.

Samples

2 1 6

4

Note

Sample is (1,6), (2,3), (3,2), (6,1).

Resources

2015 UESTC ACM Summer Training Team Selection (4)