Tuyển chọn

Vào đầu năm học 2024-2025, trường THPT A đã tiến hành thành lập và giảng dạy cho đội tuyển học sinh giỏi Tin học cho kỳ thi học sinh giỏi cấp tỉnh. Sau khi dạy xong, nhà trường đã ra một bài toán để lựa chọn \(10\) em làm tốt nhất tham dự kỳ thi.

Cho ba số nguyên dương \(n, r, k\). Gọi \(D(x)\) là tập hợp các số nguyên dương đôi một khác nhau và là ước của \(x\). Hãy tính:

\[\sum_{x=1}^{n} \sum_{d \in D(x)} r^d d^k \bmod M\]

Trong đó \(\bmod\) là phép chia lấy dư và \(M = 998244353\).

Yêu cầu: Em hãy lập trình để giải bài toán trên.

Input

Dữ liệu vào Dữ liệu vào gồm một dòng duy nhất chứa ba số nguyên dương \(n, r, k\).

Ràng buộc:

\(25\%\) số test ứng với \(25\%\) số điểm: \(n \le 10^2\); \(r = 1\); \(k \le 8\).
\(25\%\) số test ứng với \(25\%\) số điểm: \(n \le 10^6\); \(r = 1\); \(k \le 8\).
\(25\%\) số test ứng với \(25\%\) số điểm: \(n \le 2 \times 10^6\); \(r < M\); \(k \le 3 \times 10^3\).
\(25\%\) số test còn lại ứng với \(25\%\) số điểm: \(n \le 2 \times 10^9\); \(r = 1\); \(k \le 4\).

Output

In ra một số nguyên duy nhất là kết quả bài toán.

Example 1

Input:

4 1 2

Output:

Example 2

Input:

4 2 2

Output:

Note

Ví dụ 1: \(n = 4\), \(r = 1\), \(k = 2\); \(x\) lần lượt nhận các giá trị \(1, 2, 3, 4\) với các ước tương ứng: \(\{1\}\); \(\{1, 2\}\); \(\{1, 3\}\); \(\{1, 2, 4\}\). Áp dụng công thức:

\[[1^1 \times 1^2 + (1^1 \times 1^2 + 1^2 \times 2^2) + (1^1 \times 1^2 + 1^3 \times 3^2) + (1^1 \times 1^2 + 1^2 \times 2^2 + 1^4 \times 4^2)] \bmod 998244353 = 37.\]

Ví dụ 2: tương tự với \(r = 2\):

\[[2^1 \times 1^2 + (2^1 \times 1^2 + 2^2 \times 2^2) + (2^1 \times 1^2 + 2^3 \times 3^2) + (2^1 \times 1^2 + 2^2 \times 2^2 + 2^4 \times 4^2)] \bmod 998244353 = 368.\]

Điều hướng chính

Ngôn ngữ

Phím tắt