#P5014. 水の三角(修改版)

水の三角(修改版)

题目背景

这个三角图真好看。。

这个是 4{\rm 4} 阶三角图。。

题目描述

现在我们定义一个三角图是像上面一样的图。。

请求出一个无限大的三角图从 11 号点走到 uu 号点的方案数。

TT 组询问。

输入格式

第一行一个正整数 TT

第二行 TT 个正整数 uiu_i

输出格式

TT 行,共 TT 个正整数,表示答案模 998244353998244353 的结果。

3
1 3 6

1
2
6

提示

Subtask1(10 pts){\rm Subtask 1(10\ pts)}:1T100,1ui551 \leq T \leq 100, \qquad 1 \leq u_i \leq 55

Subtask2(20 pts){\rm Subtask 2(20\ pts)}:1T100,1ui125025001 \leq T \leq 100, \qquad 1 \leq u_i \leq 12502500

Subtask3(30 pts){\rm Subtask 3(30\ pts)}:$1 \leq T \leq 100, \qquad 1 \leq u_i \leq 500000500000 \qquad u_i=\frac{x \times (x + 1)}{2}$

Subtask4(40 pts){\rm Subtask 4(40\ pts)}:$1 \leq T \leq 100, \qquad 1 \leq u_i \leq 500000500000$