Lottery

문제

Jack spends a lot of time and money playing the lottery.

The lottery machine consists of $NN$ parallel ramps (as shown on the figure). Each ramp is divided into $MM$ sections of equal lengths. Under the ramps are $MM$ baskets, each labeled with an integer.

The drawing works as follows. First some ramp sections from among the $N\cdot MN\; \backslash cdot\; M$ are removed. For each section, a $BB$-sided die (with the sides numbered $1,\dots ,B1,\; \backslash ldots,\; B$) is rolled and if the result is at most $AA$, the section is removed. After that, a ball is released from the top-left corner of the machine, above the topmost ramp. If the ball ends up in a basket, the player's prize is the amount written on the basket.

[이미지 1][이미지 2]

You try to explain to Jack that in general, he always loses money in such games. To prove your point, you want to compute the expected average value of the prize of this game.

It can be shown that the expected value can be expressed as $\frac{p}{q}\backslash frac\{p\}\{q\}$ where $pp$ and $qq$ are integers and $\frac{p}{q}\backslash frac\{p\}\{q\}$ is an irreducible fraction. Compute the value $pr({10}^9+7)pr\; \backslash bmod\; (10^9\; +\; 7)$ where $rr$ is such an integer that $qr({10}^9+7)=1qr\; \backslash bmod\; (10^9\; +\; 7)\; =\; 1$.

입력

The first line contains space-separated integers $NN$ and $MM$ ($2\le N,M\le 5\cdot {10}^{5}2\; \backslash le\; N,\; M\; \backslash le\; 5\; \backslash cdot\; 10^5$), the dimensions of the lottery machine. The second line contains space-separated integers $AA$ and $BB$ (, $B\mathrm{\ne }0B\; \backslash ne\; 0$), the parameters of the die rolls.

The third line contains $MM$ space-separated integers $C_1,C_2,\dots ,C_{M}C\_1,\; C\_2,\; \backslash ldots,\; C\_M$ ($0\le C_i\le {10}^{9}0\; \backslash le\; C\_i\; \backslash le\; 10^9$ for each $ii$), the values of the baskets from left to right.

출력

Output a single integer: the expected value of Jack's prize, in the format described above.

힌트

To format your output in this task, you need to compute $rr$ such that $qr\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}K)qr\; \backslash equiv\; 1\; \backslash pmod\{K\}$ (in our case, $K={10}^9+7K\; =\; 10^9\; +\; 7$). This number is called the inverse of $qq$ modulo $KK$; it can be shown that if $q\equiv ̸0(\mathrm{m}\mathrm{o}\mathrm{d}K)q\; \backslash not\backslash equiv\; 0\; \backslash pmod\{K\}$ and $KK$ is prime, then $rr$ can be computed as $r=q^{K-2}Kr\; =\; q^\{K\; -\; 2\}\; \backslash bmod\; K$.