题目背景

墓园的骷髅海！

要塞的禁魔球！

塔楼的三后排！

据点的破甲比蒙！

地下城的满魔抗黑龙！

塔楼↑

---

燊队来打英雄无敌 3 了。

题目描述

招魂术是墓园阵营的核心法术。

拥有招魂术的英雄，在每场战争结束后，能根据消灭的敌军数目来获得一定数量的骷髅。我们可以用整数 $A,B$ 来描述招魂术。设 $F_{A,B}(i)$ 表示消灭 $i$ 个敌人所能获得的骷髅数量，有：

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

现在燊队要在酒馆招募一个英雄，英雄甲招魂术的属性为 $A,B$，英雄乙招魂术的属性为 $X,Y$。为了比较两个英雄招魂术的强弱，请你计算以下式子的值：

$$\prod_{i=1}^nF_{X,Y}(i)-F_{A,B}(i)$$

燊队当然知道怎么做，但他想考考你。

输入格式

第一行一个整数 $T$，表示询问组数。

接下来 $T$ 行，每行五个整数 $n,A,B,X,Y$。

输出格式

输出为 $T$ 行，即每组询问答案对 $998244353$ 取模的结果。

建议使用 sqrtl 和 long double 进行开平方。

4
5 2 10 1 8
11 4 5 1 4
19 1 9 8 10
114 51 4 1919 810

998244317
998242817
939523984
604148977

提示

样例说明

在样例说明中，设 $F_{A,B}$ 为 $f$，$F_{X,Y}$ 为 $g$。

对于第一组询问：

• $f$ 的前 $n$ 位为 $f=\{2,10,5,8,7\}$。

• $g$ 的前 $n$ 位为 $g=\{1,8,3,5,4\}$。

所以最终的答案为 $(1-2)\times(8-10)\times(3-5)\times(5-8)\times(4-7)=-36$，对 $998244353$ 取模后的结果是 $998244317$。

---

数据范围

对于 $40\%$ 的数据，$n \le 100$。

对于另外 $10\%$ 的数据，每组询问满足 $A=B,X=Y$。

对于另外 $10\%$ 的数据，$T=1$。

对于 $100\%$ 的数据，$1 \le A,B,X,Y,n \le 10^9$，$1 \le T \le 5\times 10^4$。