시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 1024 MB | 1 | 1 | 1 | 100.000% |
Suppose we have three chips on integer points on an infinite line (it is possible that two or more chips are at the same point). Every second one chip, taken equiprobably, moves to the next integer point (if the point was equal $x$, it becomes $x + 1$).
For each value of $t$ from $1$ to $n$, your task is to find the expected value of the maximal chip coordinate after $t$ seconds.
The first line of input contains three integers $a$, $b$, $c$ ($0 \le a \le b \le c \le 10^6$): the initial coordinates of the chips.
The second line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^6$): the maximal time we are interested in.
For each $t$ from $1$ to $n$, print a single line with a single number: the expected value of the maximal chip coordinate after $t$ seconds, expressed as an integer modulo prime number $998\,244\,353$. Formally, you can see that the expectation is a rational number $\frac{p}{q}$, where $q$ is coprime with $998\,244\,353$. You should output the number $pq^{-1}$ modulo $998\,244\,353$.
0 0 0 5
1 332748119 554580198 813384290 110916042
111 222 456 10
332748574 665496692 457 332748575 665496693 458 332748576 665496694 459 332748577