끝없는 길

무한한 수직선 위의 정수 점에 칩 세 개가 놓여 있다. 칩 두 개 이상이 같은 점에 있을 수도 있다. 매초 칩 하나를 같은 확률로 골라 다음 정수 점으로 옮긴다. 칩의 좌표가 $x$였다면 $x + 1$이 된다.

$t$를 $1$부터 $n$까지 바꿔 가며, $t$초 후 칩 좌표의 최댓값의 기댓값을 구하라.

첫 줄에 세 정수 $a$, $b$, $c$ ($0 \le a \le b \le c \le 10^6$)가 주어진다. 이는 칩들의 초기 좌표이다.

둘째 줄에 정수 $n$ ($1 \le n \le 2 \cdot 10^6$)이 주어진다. 이는 관심 있는 최대 시간이다.

$t$를 $1$부터 $n$까지 각각 구하여, 한 줄에 하나씩 출력한다. 출력값은 $t$초 후 최댓값 기댓값을 소수 $998,244,353$으로 나눈 나머지이다. 기댓값은 유리수 $\frac{p}{q}$로 나타나며, $q$는 $998,244,353$과 서로소이다. $p q^{-1}$을 $998,244,353$으로 나눈 나머지를 출력한다.