402905: GYM100942 F GCD and LCM

It is not difficult to find out the greatest common divisor and the least common multiple of several integers. No doubt you have solved such problems ... But have you ever tried to find the integers by their greatest common divisor (GCD) and least common multiple (LCM)? Or, at least, have you determined how many of such sets do GCD and LCM have? Probably, you haven't  ...

Find out how many ordered sets of k positive integers which greatest common divisor and the least common multiple are equal to d and m respectively. For example, for k = 2, d = 2, m = 12, there are four described sets: (2, 12), (12, 2), (4, 6) and (6, 4).

The first line contains one integer k — number of integers in the sets (2 ≤ k ≤ 10¹⁸). The second line contains integers d and m — GCD and LCM of integers in the set(1 ≤ d ≤ m ≤ 10⁹).

Output the number of ordered sets by modulo (10⁹ + 9).

2
2 12

4

3
4 5

0