GCD and LCM Sum Power

Given three integers n, x, and y, compute the following sum modulo 10^9+7:

$$\sum_{i=1}^{n} \gcd(i,n)^x \; \mathrm{lcm}(i,n)^y \bmod (10^9+7)$$

Here, \(\gcd(i,n)\) denotes the greatest common divisor of \(i\) and \(n\), and \(\mathrm{lcm}(i,n)\) denotes the least common multiple of \(i\) and \(n\), which can be computed as

$$\mathrm{lcm}(i,n)=\frac{i \cdot n}{\gcd(i,n)}.$$

inputFormat

The input consists of a single line containing three space-separated integers: n (n ≥ 1), x, and y.

outputFormat

Output a single integer: the value of the sum modulo 10^9+7.

sample

1 1 1

1