목공 Batch Compilation commands

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

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

입력

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

다음 $N$개의 줄의 $i$번째 줄에는 나무 상자를 분해했을 때, 나무 판자 $i-1$개를 얻게 되는 확률을 의미하는 음이 아닌 정수 $q_{i-1} $이 주어진다. $q_{0} + q_{1} + ... + q_{N - 1}$은 $1$ 이상 $10^{9}$ 이하임이 보장된다.

부분문제

부분문제	점수	N	M
1	4	1 ≤ N ≤ 1,000	0 ≤ M ≤ 5,000
2	96	1 ≤ N ≤ 16,000	0 ≤ M ≤ 1012

출력

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

입출력 예제

예제 1

입력

2 3
1
1

출력

546308098

예제 2

입력

3 6
10
10
1

출력

933814619

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