Description

Cute Theresa hopes you can help her compute the value of

$$\sum_{x = 1}^n\sum_{y = 1}^n\sum_{i = 1}^x[x \bot k_1][i \bot x]\cdot i\cdot \sum_{j = 1}^y[y \bot k_2][j \bot y]\cdot j$$

where

$$[x \bot y] = \begin{cases}1 & \operatorname{gcd}(x,y)=1 \\ 0 & \operatorname{gcd}(x,y)\neq 1\end{cases}$$

Theresa is so cute, how could you say no to her?

Since the answer may be very large, Theresa only wants to know the result modulo $998244353$.

Input Format

A single line with three integers $n, k_1, k_2$.

Output Format

A single line with one number: the required answer modulo $998244353$.

2 2 2

1

4 2 2

16

Hint

The test point numbering is in reverse order.

Constraints for all data:

• $1 \le n, k_1, k_2 \le 2 \times 10^9$.

---

This problem uses bundled tests.

No.	Constraints	Score
$1$	$1\le n,k_1,k_2\le 100$	$10$
$2$	$1\le n,k_1,k_2\le 3000$	$20$
$3$	$1\le n,k_1,k_2\le 5\times 10^5$
$4$	No further constraints	$50$

---

• Idea: Polaris_Dane
• Solution: Polaris_Dane
• Code: Polaris_Dane
• Data: Polaris_Dane

Translated by ChatGPT 5