#P18415. Endless Road

Endless Road

Endless Road

一条无限长的直线上放有三枚棋子,初始位置均为整数。两枚或三枚棋子可以位于同一个位置。

每过一秒,从三枚棋子中等概率地选择一枚,将它从坐标 xx 移动到坐标 x+1x+1。每秒只移动所选的那一枚棋子。

对于每个 t=1,2,…,nt=1,2,\ldots,n,求经过 tt 秒后三枚棋子的最大坐标的期望值。

输入格式

第一行包含三个整数 a,b,ca,b,c,表示三枚棋子的初始坐标,满足

0≤a≤b≤c≤106.0\le a\le b\le c\le 10^6.

第二行包含一个整数 nn,满足 1≤n≤2⋅1061\le n\le 2\cdot10^6,表示需要考虑的最大时间。

输出格式

输出 nn 行。第 tt 行输出经过 tt 秒后最大坐标的期望,答案对质数 998 244 353998\,244\,353 取模。

具体地,将该期望写为有理数 p/qp/q,其中 qq 与 998 244 353998\,244\,353 互质;输出 pq−1 mod 998 244 353p q^{-1}\bmod998\,244\,353,这里 q−1q^{-1} 是模意义下的乘法逆元。

样例 1

输入:

0 0 0
5

输出:

1
332748119
554580198
813384290
110916042

样例 2

输入:

111 222 456
10

输出:

332748574
665496692
457
332748575
665496693
458
332748576
665496694
459
332748577