解题思路

怪兽本体先给一张编号为 1 的凭证。随后出现的 x 个随从各自独立、等概率地在集合 {1,2,...,12} 中掉落一种凭证（可重复）。 想要“至少收集到一整套 1~12”，等价于：在这 x 次掉落中，编号 2~12 的 11 种凭证都至少出现一次（编号 1 是否出现无要求，因为怪兽已给一张 1 号）。

令事件集合为 S={2,...,12}，对 S 做容斥：

• 若缺失 k 种（从 S 中挑），可用的编号数量为 12-k（剩余的 11-k 种 + 编号 1），对应序列数为 (12-k)^x；
• 组合数为 C(11,k)，符号交替。

题目内容

白开水战士参加一个活动，成功击败一名怪兽，获得了凭证 $1$ 。怪兽死亡后召唤了 $x$ 名随从，每个随从会随机掉落编号属于集合 {$1,2,...,12$} 的凭证(均匀随机，可能重复)。

问:白开水能收集到至少一整套编号 $1$~ $12$的凭证的概率是多少?

可以证明答案可以表示为一个不可约分数 $\frac{p}{q}$，为了避免精度问题，请直接输出整数 $(\frac{p}{q}$ $mod$ $M)$ 作为答案，其中 $M=998$ $244$ $353$ ，$q^{-1}$ 是满足 $q×q^{-1}=1$ $(mod$ $M)$ 的整数。更具体地，你需要找到一个整数 $y∈[0,M)$ 满足 $y×q$ 对 $M$ 取模等于 $p$ 。

【提示】

本题中，如果您需要使用到除法的取模，即计算 $(\frac{p}{q}$ $mod$ $M)$ 时，$q^{-1}$ 需要使用公式 $(q^{M-2}$ $mod$ $M)$ 得到。

例如，在计算 $\frac{5}{4}$ $mod$ $M$ 时，根据公式 $4^{-1}=(4^{M-2}$ $mod$ $M)= 748$ $683$ $265$，得到 $(\frac{5}{4}$ $mod$ $M)=5 × 748$ $683$ $265$ $mod$ $M = 748$ $683$ $266$ 。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 ≤T≤ 10^3)$ 代表数据组数，每组测试数据描述如下：

第一行输入一个整数 $x(1 ≤ x ≤ 10^4)$ ，表示随从数量。

除此之外，保证单个测试文件的 $x$ 之和不超过 $2 × 10^5$ 。

输出描述

对于每个测试样例，新起一行，输出一个整数，表示所求概率在模 $998$ $244$ $353$ 意义下的值。

样例1

输入

2
1
11

输出

0
756275083

说明

对于第一组测试数据，当只有 $1$ 个随从时，只能额外获得一张凭证，不可能凑齐编号 $2$ ~ $12$ 共 $11$ 张缺失凭证，因此成功概率为 $0$ 。