28690번 - 현철이의 소개팅

문제

오늘은 현철이의 소개팅이 있다. 이 소식을 들은 우영이는 현철이가 성공하도록 기도하려 현철이의 집에 찾아갔다. 그런데 우영이가 도착하니, 현철이가 입을 만한 옷들은 모두 빨래 바구니 속에 들어있어 입을 옷이 없다고 말했다. 현철이는 지금이라도 빠르게 빨래하자고 말하였다. 하지만 현철이는 빨래를 모두 마치지 않으면 집에서 나가지 않는다. 즉, 약속에 늦더라도 빨래를 모두 마쳐야만 나갈 수 있다. 이를 알고 있던 우영이는 현철이가 빠르게 빨래를 마칠 수 있게 도와주려고 한다.

현철이의 집에는 총 $n$개의 세탁물이 있다. 현철이가 세탁기에 넣을 수 있는 세탁물의 개수에는 제한이 없으며, 세탁기는 총무게의 제곱만큼의 시간 동안 빨래를 한다. 즉, 세탁기에 $g$ 무게의 세탁물들을 넣으면 $g^2$ 의 시간을 사용해 세탁기 내의 빨래를 마친다.

우영이는 현철이의 빨래 속도를 높이기 위해 세탁물을 여러 개의 바구니에 나누려고 했다. 각 세탁물은 1ドル$번부터 $n$번까지의 번호가 매겨져 있으며, 우영이는 연속한 세탁물들을 같은 바구니에 분류할 수 있다. 단, 세탁물을 $k$개의 바구니로 나누기 위해서는 주어진 상수 $c$에 대해 $c(k-1)$의 시간이 추가로 소요된다.

이때 현철이는 각 세탁물 바구니를 순차적, 개별적으로 처리한다. 현철이는 각 바구니에 있는 세탁물을 다음과 같이 두 단계로 이루어진 시행을 반복하여 처리한다.

• 1ドル$단계로, 아직 바구니에 세탁되지 않은 세탁물이 $x$개라면, 1ドル$ 이상 $x$ 이하의 정수 $y$를 균등한 확률로 선택한다.
• 2ドル$단계로, $x$개의 세탁물 중 $y$개의 세탁물을 가능한 모든 조합에 대해 균등한 확률로 선택하여 세탁기에 넣고, 세탁될 때까지 기다린다.
• 남은 세탁물이 있다면 이를 1ドル$단계부터 반복한다.

우영이가 바구니를 나누는 데에 걸리는 시간과 세탁기를 기다리는 시간 이외의 시간은 계산하지 않는다.

우영이가 빨래를 마치는 데 걸리는 시간의 기댓값을 최소화할 때, 빨래를 마치는 데 걸리는 시간의 기댓값을 구하여라.

입력

첫 번째 줄에 세탁물의 개수 $N(1\le N\le 10^6)$ 과 임의 개수의 세탁물을 하나의 바구니에 담는데 걸리는 시간 $c(0\le c\le 10^9)$가 공백으로 구분되어 주어진다.

두 번째 줄엔 1ドル$번부터 $n$번 세탁물의 무게를 나타내는 $n$개의 정수$A_i(1\le A_i\le 100)$들이 공백으로 구분되어 순서대로 주어진다.

출력

첫 줄에 빨래를 마치는 데 걸리는 시간의 기댓값을 10ドル^9+7$로 나눈 나머지를 출력한다. 단, 10ドル^9+7$은 소수이다.

기약분수 $\frac{p}{q}(p\ge 0,q>0,\gcd(p,q) =1)$를 $M$으로 나눈 나머지는 $q^{-1}$가 $q\cdot q^{-1}\equiv 1\pmod M$을 만족하는 정수, 즉 $q$의 $M$에 대한 모듈로 곱셈 역원일 때, $p\cdot q^{-1}\pmod M$로 정의한다. 만약 정수일 경우 $q=q^{-1}=1$이므로 $p\pmod M$를 의미한다.

기댓값을 10ドル^9+7$로 나눈 나머지가 유일하게 결정되는 입력만 주어진다. 즉, 답은 정수이거나 기약분수로 나타냈을 때 분모가 10ドル^9+7$과 서로소인 경우만 주어진다.

제한

힌트