현철이의 소개팅

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

현철이의 집에는 세탁물이 총 $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$번까지 세탁물의 무게를 나타내는 정수 $A_i$ ($1 \le A_i \le 100$) $n$개가 공백으로 구분되어 순서대로 주어진다.

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

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

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