목공

목공을 시작한 그는 기본기를 다지려고 나무 상자 만들기를 반복한다. 나무 상자 하나는 나무판자 $N$개를 이어 붙여 만든다. 다 만든 상자는 자리만 차지하므로 곧바로 분해해서, 나온 판자를 다음 상자에 쓴다.

상자를 분해해서 얻는 온전한 판자의 수는 항상 $N$개보다 적고, 분해가 늘 깔끔하게 되지는 않아 그 수는 확률적으로 정해진다. $0 \le i < N$인 모든 $i$에 대해 판자를 $i$개 얻을 확률은 정수 $q_i$에 비례하며, $q_i / (q_0 + q_1 + \dots + q_{N-1})$로 계산된다.

그는 지금 판자 $M$개를 가지고 있고, 더 이상 상자를 만들 수 없을 때까지 계속 상자를 만든다. 그가 만드는 상자 개수의 기댓값을 구하는 프로그램을 작성하라.

첫째 줄에 상자 하나를 만드는 데 필요한 판자의 수 $N$과 그가 가진 판자의 수 $M$이 공백으로 구분되어 주어진다.

다음 $N$개 줄 중 $i$번째 줄에는 상자를 분해해서 판자를 $i-1$개 얻을 확률에 비례하는 음이 아닌 정수 $q_{i-1}$이 주어진다.

$1 \le N \le 16000$, $0 \le M \le 10^{12}$이고, $q_0 + q_1 + \dots + q_{N-1}$은 $1$ 이상 $10^9$ 이하이다.

그가 만드는 상자 개수의 기댓값을 출력한다. 정확하게 채점하려고, 답을 기약분수 $a/b$로 나타냈을 때 $(a \times b^{-1}) \bmod 1092616193$을 대신 출력한다. 여기서 $1092616193 = 2^{21} \times 521 + 1$은 소수이고, $b^{-1}$은 이 소수를 법으로 하는 $b$의 곱셈 역원이다. 이 문제에서 주어질 수 있는 모든 입력에 대해 답은 존재한다.

첫 번째 예제의 답을 기약분수로 나타내면 $3/2$이다.