2813. CrazyCooook

【题目描述】

Cooook在考试中 (dabiao)秒掉了这样一道题：C(n,0)^2+C(n,1)^2+…+C(n,n)^2 = ?于是想调戏弱鸡室友Kiev_wx可谁知Kiev_wx竟以迅雷不及掩耳盗铃儿响叮当仁不让世界充满爱你没商量你不敢爱我爱你之势秒掉了这道题，为了试探Kiev_wx的功力，Cooook将HZ数奥的书翻了个遍，找到了类似的一道题，C(n,0)^k+C(n,1)^k+…+C(n,n)^k = ?，Kiev_wx是神犇，当然秒掉了这道题，可他的IDE被Cooook卸掉了，他很郁闷于是向你求助，由于Cooook不怀好意，所以会有多次询问。

【输入格式】

第一行为 T，k 表示T个询问

接下来T行每行一个整数n

【输出格式】

T行，每行为C(n,0)^k+C(n,1)^k+…+C(n,n)^k % 998244353 的值

【样例输入】

2 2



1



2

【样例输出】

2



6 

【提示】

数据范围

10% k<=2

50% T,n<=10000

100% k<=100,T<=1000000,n<=200000

【来源】

Cooook的脑洞