该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小$A$特别喜欢爬楼梯。

他在爬楼梯的时候，每一层台阶可能是左脚踏上去的，也可能是右脚踏上去的。

小$A$踏上第一级台阶有两种方法，左脚或右脚。

当小$A$的一只脚刚踏上第i阶台阶时，下一步的可能移动方式有：接着迈出该只脚，或是另一只脚

• 如果小$A$迈出另一只脚，那么他可以踏到第i+1或i+2或……或i+k阶台阶
• 如果小$A$仍迈出该只脚，由于重心不稳，只能踏到第i+1阶台阶

求小$A$到第n阶的方案数，答案对998244353取模

例如，假设k=2

1层：左，右 两种方法

2层：左左，左右，右左，右右 四种方法

3层：左左左，左左右，左右(2)，左右左，左右右, 右右右，右右左，右左(2)，右左右，右左左 十种方法

输入格式

第一行一个正整数T，代表数据组数

第二行一个正整数k，其含义见题目描述

接下来有T行，每行有一个正整数n，表示询问走n阶台阶的合法方案数，答案对998244353取模

输出格式

对于每组询问，输出走n阶台阶的方法总数对998244353取模的结果

【样例 1 输入】

5 
2
1
2
3
4
5

【样例 1 输出】

2
4
10
24
58

【数据范围】

对于20%的数据，$1 \leq T\leq 1, 1\leq n\leq 10, 1\leq k \leq 2$。

对于40%的数据，$1 \leq T\leq 1, 1\leq n\leq 10^3, 1\leq k \leq 5$。

对于70%的数据，$1 \leq T\leq 20, 1\leq n\leq 10^5, 1\leq k \leq 20$。

对于100%的数据，$1 \leq T\leq 10^5, 1\leq n\leq 10^6, 1\leq k \leq 20$。