"A fight? Count me in!" 要打架了，算我一个。
"Everyone, get in here!" 所有人，都过来！
小Y是一个喜欢玩游戏的OIer。一天，她正在玩一款游戏，要打一个Boss。
虽然这个Boss有 1010010^{100}10100 点生命值，但它只带了一个随从——一个只有 mmm 点生命值的“恐怖的奴隶主”。
这个“恐怖的奴隶主”有一个特殊的技能：每当它被扣减生命值但没有死亡（死亡即生命值 ≤0\leq 0≤0），且Boss的随从数量小于上限 kkk，便会召唤一个新的具有 mmm 点生命值的“恐怖的奴隶主”。
现在小Y可以进行 nnn 次攻击，每次攻击时，会从Boss以及Boss的所有随从中的等概率随机选择一个，并扣减 111 点生命值，她想知道进行 nnn 次攻击后扣减Boss的生命值点数的期望。为了避免精度误差，你的答案需要对 998244353998244353998244353 取模。
输入第一行包含三个正整数 T,m,kT, m, kT,m,k，TTT 表示询问组数，m,km, km,k 的含义见题目描述。
接下来 TTT 行，每行包含一个正整数 nnn，表示询问进行 nnn 次攻击后扣减Boss的生命值点数的期望。
输出共 TTT 行，对于每个询问输出一行一个非负整数，表示该询问的答案对 998244353998244353998244353 取模的结果。
可以证明，所求期望一定是一个有理数，设其为 p/qp / qp/q（gcd(p,q)=1\mathrm{gcd}(p,q) = 1gcd(p,q)=1），那么你输出的数 xxx 要满足 p≡qx(mod998244353)。
3 2 6 1 2 3
499122177 415935148 471393168
对于第一次询问，第一次攻击有 12\frac{1}{2}21 的概率扣减Boss的生命值，有 12\frac{1}{2}21 的概率扣减随从的生命值，所以答案为 12\frac{1}{2}21。1≡2∗499122177(mod998244353)。
对于第二次询问，如果第一次攻击扣减了Boss的生命值，那么有 12\frac{1}{2}21 的概率第二次攻击仍扣减Boss的生命值，有 12\frac{1}{2}21 的概率第二次攻击扣减随从的生命值；如果第一次攻击扣减了随从的生命值，那么现在又新召唤了一个随从（“恐怖的奴隶主”），于是有 13\frac{1}{3}31 的概率第二次攻击扣减Boss的生命值，有 23\frac{2}{3}32 的概率第二次攻击扣减随从的生命值。所以答案为 12∗12∗2+12∗12∗1+12∗13∗1+12∗23∗0=1112\frac{1}{2}*\frac{1}{2}*2+\frac{1}{2}*\frac{1}{2}*1+\frac{1}{2}*\frac{1}{3}*1+\frac{1}{2}*\frac{2}{3}*0 = \frac{11}{12}21∗21∗2+21∗21∗1+21∗31∗1+21∗32∗0=1211。11≡12∗415935148(mod998244353)。
见附加文件下的 ex_2.in 与 ex_2.ans。
该组样例的数据范围（除询问组数 TTT 外）同第7、8个测试点。
在所有测试点中，1≤T≤1000,1≤n≤1018,1≤m≤3,1≤k≤81 \leq T \leq 1000, 1 \leq n \leq {10}^{18}, 1 \leq m \leq 3, 1 \leq k \leq 81≤T≤1000,1≤n≤1018,1≤m≤3,1≤k≤8。
各个测试点的分值和数据范围如下：