뫼비우스 매드니스

뫼비우스 함수 $\mu(n)$은 정수론에서 쓰이는 중요한 곱성 함수(multiplicative function) 중 하나다.

양의 정수 $n$에 대해 $\mu(n)$은 다음과 같이 정의된다.

• $n$이 제곱 인수를 갖지 않는 양의 정수이고 소인수가 $k$개면 $\mu(n)=(-1)^k$이다. 특히 $\mu(1)=1$이다.
• $n$이 제곱 인수를 갖지 않는 양의 정수가 아니면 $\mu(n)=0$이다.

양의 정수 $N$, $L$, $K$가 주어졌을 때 다음 값을 계산하자. 값이 커지므로 $10^9+7$로 나눈 나머지를 출력한다.

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

한 줄에 양의 정수 $N$, $L$, $K$가 순서대로 주어진다.

입력은 $1 \le N \le 10^9$, $1 \le L \le 10^{15}$, $1 \le K \le 10^9$를 만족한다.

위 합의 값을 $10^9+7$로 나눈 나머지를 출력한다.