【题目描述】

将不同的颜色编号为 $0\sim n$ 。

有一条含 $n$ 个方格的纸带，初始时均为颜色 $0$。

接下来你需要进行 $n$ 次操作，第 $i$ 次操作可以选择某 $k$ 个连续方格染成颜色 $i$ 。

所有操作完成后，若相邻两个方格的颜色不同，则在它们之间折一下，留下一条折痕。求折痕的可能分布的方案数，答案对 $10^9+7$ 取模。

你需要对 $T$ 条长度不同的纸带解决上述问题。

【输入格式】

第一行两个整数，$T,k$。

第二行 $T$ 个整数 $n_{1\sim T}$ 。

【输出格式】

输出一行 $T$ 个整数，第 $i$ 个整数表示纸带长度为 $n_i$ 时的答案对 $10^9+7$ 取模的值。

【样例#1】

输入：

3 2
2 3 4

输出：

1 2 4

【样例#2】

输入：

3 3
10 20 30

输出：

224 190972 149198253

【样例#3】

见选手目录下的 $\texttt{color/color3.in}$ 与 $\texttt{color/color3.ans}$。

【数据范围和约定】

对于所有的数据，满足 $1\leq T\leq 100,1\leq k\leq 50,k\leq n_i\leq 10^{18}$。