时间限制：1000ms　内存限制：512MB

题目描述

程老师的爱人经营一家婚庆工作室，承接定制贺卡业务：每张贺卡按收信人的喜好单独设计，配同样定制、写好收信人名字的信封。工作室开了八年，定制贺卡是招牌，从选纸、烫金到手写祝词都按订单来。前阵子工作室接了一批订单，共 $n$ 张贺卡、$n$ 个信封，贺卡和信封一一对应，第 $i$ 张贺卡应当装进第 $i$ 个信封。按理说装封是最后一道工序，照着名字装就行——前提是装的人看名字。

交货前一天，工作室雇的临时工小赵负责装封。他是隔壁印刷厂介绍来的，手脚麻利，以前装的都是统一印好的贺卡，闭眼装也不会错。这回他照老经验办事，不看名字，抓起一张贺卡就往手边的信封里塞，装完最后一个信封就收工走了。这 $n$ 张贺卡分别装得对不对，谁也说不准。全部拆封检查已经来不及，第二天一早就要交货。

这批订单是国庆旺季的加急单，客户是一家连锁酒店，贺卡在婚宴上随桌牌一起发。信封上的收信人名字提前三天就写好了，原本按座位号排序，装封前这一摞贺卡和信封被来回调动过几次，顺序早就乱了，谁也说不出原来的对应关系。

程老师的爱人要估算一份售后预案：如果这批货装错得多，客户投诉会集中爆发，回访人手得提前安排。要估算，先得弄清一个理论问题——把小赵这种装法的所有可能结果都算上，恰好有 $k$ 张贺卡装进正确信封的装法，一共有多少种。她先问"全装对的有几种"，又问"只装对一张的呢""装对一半的呢"，问题越问越多。

程老师干脆决定：把她关心的 $q$ 个 $k$ 一次性都算出来，每个 $k$ 给出"恰好 $k$ 张装对"的装法总数，列成一张表贴在工作室的墙上，以后遇到同类订单直接查表，也用得上。

装法总数随 $n$ 增长得非常快，几十张贺卡时就已经写不下了。两人约定，每个答案只报告它对 $998244353$ 取模后的余数，足够了解量级就行。

为什么按"所有可能装法"来估？小赵装封不挑不拣，哪张贺卡进哪个信封全凭抓到手的顺序，每种装法在他手里出现的机会都差不多。程老师和爱人商量下来，认为这样估算最公允，问题就这么定了。

程老师起初想把所有装法逐个列出来数一数，写了个小程序，贺卡一多，程序跑到天亮也没跑完。他这才明白，得先把装法数的计算方法研究清楚，让程序只做计算、不做列举。$n$ 和 $q$ 都可能很大，这张表要当工作室的参考数据，以后每年旺季都要用，算错了可不是小事。

输入格式

第一行两个整数 $n, q$，表示贺卡（信封）数量和询问次数。

接下来 $q$ 行，每行一个整数 $k$，表示询问"恰好 $k$ 张贺卡装进正确信封"的装法数。

输出格式

输出 $q$ 行，第 $i$ 行一个整数，表示第 $i$ 个询问的答案对 $998244353$ 取模后的余数。

数据范围

• 对于全部数据，$1 \le n \le 10^5$，$1 \le q \le 10^5$，$0 \le k \le n$；同一测试点中不同的询问，$k$ 可能重复。

样例

样例 1

输入：

3 3
0
1
2

输出：

2
3
0

解释：$3$ 张贺卡共 $6$ 种装法，逐个数：$(1,2,3)$ 全对，$0$ 张错；$(1,3,2)$、$(3,2,1)$、$(2,1,3)$ 各装对 $1$ 张；$(2,3,1)$、$(3,1,2)$ 一张都不对。所以恰好 $0$ 张对的有 $2$ 种，恰好 $1$ 张对的有 $3$ 种。恰好 $2$ 张对的呢？剩最后一张没得选，只能进剩下的信封，也就跟着对了——两张对必然三张全对，所以一种都没有，答案是 $0$。

样例 2

输入：

4 2
0
4

输出：

9
1

解释：$4$ 张贺卡一张都不装对的装法有 $9$ 种（不信可以把 $24$ 种装法全列出来逐个数）；四张全装对的只有 $(1,2,3,4)$ 这 $1$ 种。

样例 3

输入：

5 2
1
3

输出：

45
10

解释：$5$ 张贺卡恰好装对 $1$ 张：先定哪一张对（$5$ 种选法），剩下 $4$ 张一张都不能对（由样例 2 知有 $9$ 种），共 $5 \times 9 = 45$ 种。恰好装对 $3$ 张：定哪 $3$ 张对有 $10$ 种选法，剩下 $2$ 张必须全错，只能互换，$1$ 种，共 $10 \times 1 = 10$ 种。