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)

• p denotes 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)

• x is 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.