P10084 [GDKOI2024 Senior] Calculation

Define $F(x, a, b) = \gcd(x^a - 1, x^b - 1) + 1, x > 0$. In particular, if $a = 0$ or $b = 0$, then $F(x, a, b) = 0$. Now you are given five non-negative integers $m, a, b, c, d$. Let $L = F(m, a, b) + 1$ and $R = F(m, c, d)$. Ask how many subsets of the set $\{L, L + 1, L + 2, \dots, R - 2, R - 1, R\}$ have a subset sum that is a multiple of $m$. Since the answer may be very large, you only need to output the result modulo $998244353$. **Because the third batch of testdata is incorrect, in particular, if $L > R$, output $1$.**

The first line contains an integer $T$, the number of test cases. The next $T$ lines each contain five non-negative integers $m, a, b, c, d$.

For each test case, output the answer.

**[Sample Explanation]** After calculation, we have $L=1$ and $R=5$. The set is $1,2,3,4,5$. There are $8$ subsets whose subset sums satisfy the condition: $\{\}$, $\{5\}$, $\{2, 3\}$, $\{1, 4\}$, $\{1, 2, 3, 4\}$, $\{2, 3, 5\}$, $\{1, 4, 5\}$, $\{1, 2, 3, 4, 5\}$. **[Constraints]** ::cute-table{tuack} | Test Point ID | $m$ | $L,R$ | $a,b$ | $c,d$ | $T$ | Special Properties | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $=2$ | $L=1,R=2$| $=0$ | $\leq 10$ | $\leq 5$ | None | | $2$ | $\leq 10$ |$L=1,R=m$ | ^ | ^ | ^ | ^ | | $3$ | $\leq 5$ | $\leq 10^3$ | $\le 10$ | ^ | ^ | $1$ | | $4\sim 6$ | $\leq 20$ | $\leq 2\times 10^3$ | ^ | ^ | ^ | None | | $7$ | ^ | $\leq 10^5$ | $\leq 10^2$ | $\leq 10^2$ | ^ | $2$ | | $8,9$ | $\leq 80$ | $\leq 10^9$ | ^ | ^ | ^ | None | | $10\sim 13$ | $\leq 2\times 10^3$ | $\leq 10^{18}$ | $\leq 10^3$ | $\leq 10^3$ | ^ | ^ | | $14\sim 17$ | $\leq 10^5$ | ^ | ^ | ^ | ^ | ^ | | $18\sim 20$ | $\leq 10^7$ | ^ | ^ | ^ | $\leq 10^4$ | ^ | - Special Property 1: $R - L + 1 \leq 20$. - Special Property 2: $R - L + 1 \leq 2000$. For all data, it is guaranteed that $L < R$ and $m > 0$. Translated by ChatGPT 5