목공 Batch 컴파일 명령

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

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

입력

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

다음 N개의 줄의 i번째 줄에는 나무 상자를 분해했을 때, 나무 판자 i-1개를 얻게 되는 확률을 의미하는 음이 아닌 정수 q_i-1 이 주어진다. q₀ + q₁ + ... + q_N - 1은 1 이상 10⁹ 이하임이 보장된다.

부분문제

출력

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

입출력 예제

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