Problem Description
You are given $n$ queries. For each query, you are given an integer $x$, and you need to calculate the multiplicative inverse of $x$ in $\mathbb{F}_{998\,244\,353}$. In other words, you need to find the integer $y \in [0, 998\,244\,353)$ where $x \cdot y \equiv 1 \pmod {998\,244\,353}$.
You have to answer all queries online.
Implementation Details
You need to include the file inv.h and implement the following functions:
void init(int p)pdenotes the modulus in this problem, which will always be $998\,244\,353$.- The function will be called exactly one at the beginning of each test case.
int inv(int x)xis the number given in this query.- You need to return the multiplicative inverse of $x$ in $\mathbb F_{998\,244\,353}$.
The function inv will be called exact $n$ times.
Scoring
For all test cases, $1 \leq n \leq 10^8$, $p = 998\,244\,353$.
- Subtask 1(10 Points): $n \leq 10^5$
- Subtask 2(20 Points): $n \leq 10^7$
- Subtask 3(30 Points): $n \leq 5 \times 10^7$
- Subtask 4(20 Points): $n \leq 8 \times 10^7$
- Subtask 5(20 Points): No additional constraints.