UOJ Logo

NOI.AC

2S 666MB
Statistics

Lyra 新进入了一家自动飞行公司开始了实习,作为一名同时精通算法,系统,硬件的天才,她刚入职了两周就设计了一种自动飞行蜻蜓的模型。与无限撞玻璃的普通昆虫不同,这种蜻蜓可以自动识别出房间的门并从中穿过。

Lyra 甚至宣称,这种蜻蜓还对路线有完整的把握,可以时时刻刻知道自己在哪并规划路径。

为了演示这种蜻蜓的飞行技术,Lyra 设计了 $n$ 个房间,每个房间有左右两个门,两个门走出去都会进入一个单向通道,并从烟囱落入另一个房间,换言之,对于编号为 $i \in [1, n]$ 的房间,有两个属性 $L_i, R_i \in [1,n]$,若从左边的门出去则会飞到第 $L_i$ 个房间,而若从右边的门出去则会飞到第 $R_i$ 个房间(注意 $L, R$ 不一定是排列)。

虽然房间系统非常复杂,Lyra 宣称她的电子蜻蜓依然可以在穿过错综复杂的通道系统后回到自己的房间,可就在 Demo 前一天,Lyra 还没有开始写位置记录系统,情急之下 Lyra 决定让蜻蜓按照如下的方法飞行:

重复 $A$ 次:走左边的门;

再走右边的门;

再重复 $B$ 次:走左边的门;

再走右边的门;

再重复 $C$ 次:走左边的门。

Lyra 发现只要自己精心设计房间的通道系统(即 $L_i, R_i$),电子蜻蜓无论从哪个房间出发,经过这一系列操作后都会回到原来的房间,这样就能混过 Demo 了。

Lyra 还很好奇一共有多少种不同的通道系统可以做到这样呢?两种系统被认为不同当且仅当存在 $i$ 使得对应的 $L_i$ 或 $R_i$ 不同。

输入格式

第一行一个整数 $T$ 表示数据组数。

接下来 $T$ 行 每行四个整数 $n, A, B, C$,意义如题所述。

输出格式

对于每个输入输出一行一个整数表示答案对 $998244353$ 取模的结果。

样例输入输出

样例输入1

3
3 1 1 1
5 2 3 4
20 13 18 100

样例输出1

6
600
17287547

样例解释1

对于第一组数据,可行的六种方案是:

$L = \{1, 2, 3\}, R = \{1, 2, 3\}$

$L = \{1, 2, 3\}, R = \{1, 3, 2\}$

$L = \{1, 2, 3\}, R = \{2, 1, 3\}$

$L = \{1, 2, 3\}, R = \{3, 2, 1\}$

$L = \{2, 3, 1\}, R = \{1, 2, 3\}$

$L = \{3, 1, 2\}, R = \{1, 2, 3\}$

数据范围及约定

对于 $5\%$ 的数据,$n \leq 5$;

对于 $15\%$ 的数据,$n \leq 8$;

对于 $25\%$ 的数据,$n \leq 10$;

对于 $35\%$ 的数据,$n \leq 20$;

对于 $55\%$ 的数据,$n \leq 50$;

对于 $75\%$ 的数据,$n \leq 400$;

对于 $100\%$ 的数据 $1 \leq T \leq 10; 1 \leq n \leq 1000; 0 \leq A, B, C \leq 10^{18}.$

时间限制:$2\texttt{s}$

空间限制:$666\texttt{MB}$

下载

样例数据下载