Woodworking

He has taken up woodworking and builds the same wooden box over and over to practice the basics. One box takes $N$ planks joined together. A finished box only takes up space, so he takes it apart right away and uses the planks for the next box.

Taking a box apart always yields fewer than $N$ intact planks, and the joints do not always come apart cleanly, so the count is random. For every $i$ with $0 \le i < N$, the probability of recovering exactly $i$ planks is proportional to an integer $q_i$, and equals $q_i / (q_0 + q_1 + \dots + q_{N-1})$.

He currently holds $M$ planks and keeps building boxes until he can no longer build one. Write a program that computes the expected number of boxes he builds.

The first line contains two integers $N$ and $M$, separated by a space: the number of planks one box needs, and the number of planks he holds.

The $i$-th of the next $N$ lines contains one nonnegative integer $q_{i-1}$, the weight of recovering exactly $i-1$ planks from a disassembled box.

$1 \le N \le 16000$, $0 \le M \le 10^{12}$, and $q_0 + q_1 + \dots + q_{N-1}$ is between $1$ and $10^9$.

Print the expected number of boxes he builds. To keep grading exact, write the answer as a reduced fraction $a/b$ and print $(a \times b^{-1}) \bmod 1092616193$ instead. The modulus $1092616193 = 2^{21} \times 521 + 1$ is prime, and $b^{-1}$ is the multiplicative inverse of $b$ modulo that prime. The answer exists for every input allowed here.

The answer to the first sample, written as a reduced fraction, is $3/2$.