P8956 "CGOI-3" Necromancy

A sea of skeletons in the Necropolis! The anti-magic ball of the Stronghold! The three back-row shooters of the Tower! The armor-piercing Behemoth of the Fortress! The full magic-resistance Black Dragon of the Dungeon!  ###### Tower ↑ ----- Team Shen is here to play Heroes of Might and Magic 3.

Necromancy is the core spell of the Necropolis faction. A hero with Necromancy can gain a certain number of skeletons after each battle, based on the number of enemies killed. We use integers $A,B$ to describe Necromancy. Let $F_{A,B}(i)$ denote the number of skeletons obtained by killing $i$ enemies. Then: $$F_{A,B}(1)=A,F_{A,B}(2)=B,F_{A,B}(x)=\lfloor \sqrt{F_{A,B}(x-2)F_{A,B}(x-1)}\rfloor+1\;(x \ge 3)$$ Now Team Shen wants to recruit a hero in the tavern. Hero 1 has Necromancy parameters $A,B$, and Hero 2 has Necromancy parameters $X,Y$. To compare whose Necromancy is stronger, compute the value of the following expression: $$\prod_{i=1}^nF_{X,Y}(i)-F_{A,B}(i)$$ Of course Team Shen knows how to do it, but he wants to test you.

The first line contains an integer $T$, the number of queries. The next $T$ lines each contain five integers $n,A,B,X,Y$.

Output $T$ lines. For each query, output the answer modulo $998244353$. It is recommended to use `sqrtl` and `long double` for square roots.

#### Sample Explanation In the sample explanation, let $F_{A,B}$ be $f$, and $F_{X,Y}$ be $g$. For the first query: - The first $n$ terms of $f$ are $f=\{2,10,5,8,7\}$. - The first $n$ terms of $g$ are $g=\{1,8,3,5,4\}$. So the final answer is $(1-2)\times(8-10)\times(3-5)\times(5-8)\times(4-7)=-36$, and the result modulo $998244353$ is $998244317$. --- #### Constraints For $40\%$ of the testdata, $n \le 100$. For another $10\%$ of the testdata, each query satisfies $A=B,X=Y$. For another $10\%$ of the testdata, $T=1$. For $100\%$ of the testdata, $1 \le A,B,X,Y,n \le 10^9$ and $1 \le T \le 5\times 10^4$. Translated by ChatGPT 5