#2018106. 染色

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Neworld2002

题目描述

fjzzq2002有n个板砖排成一列。

为了能分清楚每块板砖用来秒掉哪种类型的题(雾),他需要把板砖染色。他手上有红色、蓝色和绿色颜料可以染色。

其中,用红色染一块板砖可以得到A的能力加成;用蓝色染一块板砖可以得到B的能力加成;用绿色染一块板砖可以得到C的能力加成。

板砖可以不染色,这样这块板砖就不会贡献任何的能力加成。

为了使得能力加成正好为x,有几种染法。(注:只要有一个位置的板砖颜色不同就算不同的染法)。

良心出题人为了让这题成为签到题,保证,且答案对998244353取模。

【输入格式】

输入文件名为color.in。

第一行,一个数T,表示数据组数。

接下来每组数据一行:对于每组数据,一行4个数,,含义如题目所示。

输入格式

输入文件名为color.in。

第一行,一个数T,表示数据组数。接下来每组数据一行:

对于每组数据,一行4个数,,含义如题目所示。

输出格式

输出文件名为color.out。

对于每组数据,输出一行,一个数,表示答案。

样例

1

4 1 2 5


40

数据范围与提示

t<=10

1<=n,A,B<=300000

1<=x<=1.8*10^11

sigma n<=300000

(数据很水)