假设我们在无限长的直线上有三个筹码，它们位于整数坐标点上（两个或多个筹码可能位于同一点）。每一秒钟，随机等概率地选择一个筹码，将其移动到下一个整数坐标点（如果当前坐标为 $x$，则变为 $x + 1$）。

对于从 $1$ 到 $n$ 的每个 $t$，你的任务是求出 $t$ 秒后三个筹码坐标最大值的期望。

输入格式

第一行包含三个整数 $a, b, c$ ($0 \le a \le b \le c \le 10^6$)，表示筹码的初始坐标。

第二行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^6$)，表示我们感兴趣的最大时间。

输出格式

对于每个从 $1$ 到 $n$ 的 $t$，输出一行，包含一个数字：$t$ 秒后筹码坐标最大值的期望，结果对质数 $998\,244\,353$ 取模。形式化地说，期望是一个有理数 $\frac{p}{q}$，其中 $q$ 与 $998\,244\,353$ 互质。你需要输出 $pq^{-1} \pmod{998\,244\,353}$。

样例

样例输入 1

0 0 0
5

样例输出 1

1
332748119
554580198
813384290
110916042

样例输入 2

111 222 456
10

样例输出 2

332748574
665496692
457
332748575
665496693
458
332748576
665496694
459
332748577