P9007 [Beginner Contest #9] The Clearest Sky and Sea (Hard Version)

Material 1: > Please carefully compute the following expression: $138 - 108 \div 6 = ?$ > You may find it hard to believe that the result of this expression is actually $5!$ Material 2: > For a positive integer $x$, $x! = 1 \times 2 \times \cdots \times (x - 1) \times x$. We call $x!$ the factorial of $x$. > In particular, $0! = 1$. Obviously, “$138 - 108 \div 6 = 5$” is wrong, while “$(138 - 108) \div 6 = 5$” is correct. So for the content in Material 1, some readers may think “the author made a mistake because they did not understand the priority order of $+$, $-$, $\times$, and $\div$.” However, the exclamation mark in the last line of Material 1 is not punctuation, but the “factorial” mentioned in Material 2. With this in mind, “$138 - 108 \div 6 = 5! = 1 \times 2 \times \cdots \times 5 = 120$” is clearly correct.

However, this problem may not be closely related to the background above. We will give you $T$ test cases, and each test case contains a positive integer $n$. For each test case, please help compute the number of integer triples $(x, y, z)$ that satisfy the following conditions: 1. $x \geq 0$, $z \geq 1$. 2. $x - y \div z = n!$ and $(x - y) \div z = \dfrac{n!}{n}$. Since the answer may be very large, you need to output the result modulo $998244353$. It is not hard to notice that the answer may be $\infty$. In that case, please handle it according to the “Output Format.” **Note that here it must satisfy $(x - y) \div z = \dfrac{n!}{n}$, not $= n$.** Also note that $\div$ here is not floor division. This clearly means you must ensure that $y \div z$ and $(x - y) \div z$ are integers.

The input has $T + 1$ lines. The first line contains an integer $T$. The next $T$ lines each contain one integer $n$.

Output $T$ lines, each being an integer or a string. For the $i$-th line: if for the given $n$ on line $i + 1$ of the input, there are infinitely many integer triples $(x, y, z)$ satisfying $x - y \div z = n!$ and $(x - y) \div z = \dfrac{n!}{n}$, output `inf`. Otherwise, output the number of triples satisfying the conditions modulo $998244353$.

### Explanation for Sample 1 The specific triples in the sample are as follows: | $n$ | All possible triples | | :----------: | :----------: | | $2$ | $(2, 0, 2)$ | | $3$ | $\begin{matrix}(8, 4, 2) & (5, -5, 5) & (6, 0, 3)\end{matrix}$ | | $4$ | $\begin{matrix}(19, -95, 19) & (21, -21, 7) & (24, 0, 4) \\ (27, 9, 3) & (20, -40, 10) & (36, 24, 2)\end{matrix}$ | ### Constraints For the first $20\%$ of the testdata, it is guaranteed that $T \leq 10$ and $n \leq 10$. For the first $40\%$ of the testdata, it is guaranteed that $n \leq 10 ^ 3$. For another $20\%$ of the testdata, it is guaranteed that $T = 1$. For $100\%$ of the testdata, it is guaranteed that $1 \leq T \leq 10 ^ 5$ and $1 \leq n \leq 10 ^ 6$. Translated by ChatGPT 5