P7504 "HMOI R1" Cute Theresa

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

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$.

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

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

**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$ | $20$ | | $4$ | No further constraints | $50$ | --------------- - Idea: Polaris_Dane - Solution: Polaris_Dane - Code: Polaris_Dane - Data: Polaris_Dane Translated by ChatGPT 5