Problem Description

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$.

Input Format

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$.

Output Format

For each test case, output the answer.

3
5 0 0 2 1
4 1 2 2 4
8 3 2 4 6

8
1024
527847872

Hint

[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}

• 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