Đếm số dãy ~a~ nguyên dương độ dài ~n~ thỏa mãn:

• ~1 \leq a_i \leq m~

• ~gcd(a_1, a_2, \dots, a_n) = k~.

Input

Dòng duy nhất nhập ~3~ số nguyên dương ~n, m, k (1 \leq n, m, k \leq 10^6)~.

Output

In ra số dãy ~a~ thỏa mãn điều kiện.

Vì đáp án có thể rất lớn, in ra số dãy modulo ~998244353~.

Scoring

Sample Input 1

3 4 2

Sample Output 1

7

Notes

Có các dãy ~a~ sau thỏa ~gcd(a_1, a_2, a_3) = 2~:

• ~(2, 2, 2)~

• ~(4, 2, 2)~

• ~(2, 4, 2)~

• ~(2, 2, 4)~

• ~(4, 4, 2)~

• ~(4, 2, 4)~

• ~(2, 4, 4)~