Background

Polaris_Dane is very keen on math. He is not only obsessed with number theory, but also likes playing Honkai Impact 3.

Problem 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