시간 제한메모리 제한제출정답맞힌 사람정답 비율
7 초 512 MB70321945.238%

문제

목공을 시작한 그는 기본기를 쌓기 위해 나무 상자를 만드는 것을 반복하고자 한다. 나무 상자 하나는 N개의 나무판자를 이어 붙여 만들 수 있다. 이렇게 만들어진 나무 상자는 어차피 공간만 차지하므로 다시 나무판자로 분해하여 새로운 나무 상자를 만들기 위해 사용한다. 나무 상자를 분해하여 새로 얻을 수 있는 온전한 나무판자의 수는 N개보다 작으며(N개 미만), 상자를 언제나 잘 분해할 수는 없기에 그는 확률적으로 나무판자를 얻게 된다. 모든 0 ≤ i < N에 대해 나무 상자를 분해하여 나무판자 i개를 얻을 확률은 정수 qi에 비례함이 알려져 있으며, qi/(q0 + q1 + ... + qN-1)로 계산된다.

그는 현재 M개의 나무판자를 가지고 있으며, 나무 상자를 만들 수 없을 때까지 계속해서 나무 상자를 만들 것이다. 그가 만들게 되는 나무 상자 수의 기댓값을 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 나무 상자를 만드는데 필요한 나무 판자의 수와 그가 가지고 있는 나무 판자의 개수를 나타내는 두 자연수 N과 M이 공백으로 구분되어 주어진다.

다음 N개의 줄의 i번째 줄에는 나무 상자를 분해했을 때, 나무 판자 i-1개를 얻게 되는 확률을 의미하는 음이 아닌 정수 qi-1 이 주어진다. q0 + q1 + ... + qN-1은 1 이상 109 이하임이 보장된다. (1 ≤ N ≤ 16,000, 0 ≤ M ≤ 1012)

출력

그가 만들게 되는 나무 상자 개수의 기댓값을 출력한다. 정확한 판별을 위해, 답을 기약분수로 나타내었을 때 a/b가 된다면, (a × b-1) mod 1,092,616,193(= 221 × 521 + 1이며, 소수이다)을 대신 출력하도록 한다. b-1은 b의 모듈러 곱셈에 대한 역원이다. 이 문제에서는 가능한 모든 입력에 대해 답이 존재한다.

예제 입력 1

2 3
1
1

예제 출력 1

546308098

예제 입력 2

3 6
10
10
1

예제 출력 2

933814619

힌트

첫 번째 예제의 답은 3/2를 나타낸다.

출처

Contest > kriiicon > 제4회 kriiicon 5번