Bedao Regular Contest 17 - Dãy số

View as PDF

Submit solution


Points: 0.60 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Đế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

Subtask Điểm Giới hạn
1 ~20~ ~n, m, k \le 100~
2 ~80~ Không ràng buộc gì thêm

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)~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.