Given integers $N$ and $r$, find the number of ordered sextuplets $(a, b, c, a', b', c')$ such that the following congruence equations hold: $ab+a'b'\equiv bc+b'c'\equiv ca+c'a'\equiv r\pmod N$ where $a, b, c, a', b', c' \in \{0, 1, \dots, N-1\}$.
It is guaranteed that $\mu(N) \neq 0$, meaning that the exponent of every prime factor of $N$ is $1$.
Input
Two integers $N$ and $r$.
Output
A single integer representing the answer. The answer should be taken modulo $998\,244\,353$.
Examples
Input 1
2 0
Output 1
20
Input 2
15 1
Output 2
3472
Subtasks
For all test cases, it is guaranteed that $0 \le r < N \le 10^{18}$, $N \ge 2$, and $\mu(N) \neq 0$.
| Subtask ID | Score | $N \leq$ | Special Constraints |
|---|---|---|---|
| $1$ | $7$ | $50$ | None |
| $2$ | $8$ | $500$ | |
| $3$ | $15$ | $10^7$ | |
| $4$ | $20$ | $10^{10}$ | $r=0$ |
| $5$ | $20$ | $r=1$ | |
| $6$ | $10$ | $10^{18}$ | $N$ is prime |
| $7$ | $20$ | None |