Möbius Madness

The Möbius function $\mu(n)$ is one of the important multiplicative functions in number theory.

For a positive integer $n$, $\mu(n)$ is defined as follows.

• If $n$ is squarefree and has $k$ prime factors, then $\mu(n)=(-1)^k$. In particular, $\mu(1)=1$.
• If $n$ is not squarefree, then $\mu(n)=0$.

Given positive integers $N$, $L$, and $K$, compute the following value. Since the value can be large, print it modulo $10^9+7$.

$\sum_{d=1}^N \mu(L \cdot d) \left\lfloor \frac{N}{d} \right\rfloor^K$

The input is a single line containing the positive integers $N$, $L$, and $K$, in that order.

The input satisfies $1 \le N \le 10^9$, $1 \le L \le 10^{15}$, and $1 \le K \le 10^9$.

Print the value of the sum above modulo $10^9+7$.