Background

Problem Description

You are given a $ka\times kb\times kc\times kd$ four-dimensional grid, where each cell can only be black or white.
How many coloring schemes are there such that, in every $k\times k\times k\times k$ subgrid, there are exactly $1$ black cell?

Since the answer may be very large, you only need to output the result modulo $998244353$.

Input Format

The first line contains an integer $T$, the number of test cases.
The next $T$ lines each contain five integers $k,a,b,c,d$, and it is guaranteed that $a\le b\le c\le d$.

Output Format

Output $T$ lines, each containing one integer: the number of schemes modulo $998244353$.

1
3 2 2 2 2

744944653

Hint

Sample Explanation

See Coloring³ for details.

Constraints and Notes

For $100\%$ of the testdata: $1\le T\le3$, $1\le k<998244353$, $2\le a\le b\le c\le d\le 10^{18}$.
To prevent you from “cheating the testdata”, such as by looking at the returned results or using binary search to recover the input.
Therefore, this problem uses a Special Judge, and each evaluation uses random testdata.
Later I was reminded that the Special Judge can directly remove returned information, and the data you get is useless anyway. I’m an idiot.

It is guaranteed that each test point can be finished within $5\text{ms}$, see the judge records. I was still too kind.

Translated by ChatGPT 5