Description

Since the problem setter is too lazy to write a background, let's keep the problem simple.

Given two integers $p$ and $n$, compute:

$$\left(\sum_{i=1}^n\sum_{j=1}^n ij \gcd(i,j)\right) \bmod p$$

Here $\gcd(a,b)$ denotes the greatest common divisor of $a$ and $b$.

Input Format

A single line containing two integers $p$ and $n$.

Output Format

Output a single integer on one line, the answer.

998244353 2000

883968974

Hint

For 20% of the testdata, $n \leq 1000$.

For 30% of the testdata, $n \leq 5000$.

For 60% of the testdata, $n \leq 10^6$, time limit 1 s.

For another 20% of the testdata, $n \leq 10^9$, time limit 3 s.

For the last 20% of the testdata, $n \leq 10^{10}$, time limit 4 s.

For 100% of the testdata, $5 \times 10^8 \leq p \leq 1.1 \times 10^9$ and $p$ is prime.

Translated by ChatGPT 5