Liu Kanshan loves jumping steps!

Now in front of Liu there're $n$ steps. He stands on the 0th step and wants to jump to the $n$-th step. He can only jump up (from the $x$-th step to the $x+k$-step, for any positive integer $k$). For one jump, he gets a score of $k^2$.

However, $m$ of these steps are broken and Liu can't jump onto them. The broken steps are $p_1,p_2,\cdots,p_m$.

Also, if Liu jumps over more than $S$ broken steps in one jump (that means $\sum\limits_{i=1}^m[x<p_i<y]>S$, where $x$ and $y$ are the start position and the end position of this jump), he won't get the score for this jump because of overwork. Note that the score he gets before won't be cleared.

Now Liu wonders what is the sum of the total scores he can get in all different possible ways of jumping. Two ways of jumping are different if and only if there exists a step that it is jumped on in one way, and not jumped on in the other way. Since the answer may be very large, you need to find it modulo $10^9+7$.

The first line contains three integers $n$, $m$ and $S (1\leq n \leq 10 ^ 9, 0\leq S\leq m\leq 2\times 10 ^ 6)$.

The second line contains $m$ integers $p_1, p_2, \cdots, p_m (0 < p_1 < p_2 \cdots < p_m < n)$.

The only line contains one integer: the answer modulo $10^9+7$.

Let $q$ be the sequence of steps Liu jumps on. There are 8 ways of jumping:

1. $q={0, 1, 3, 5, 6}$, the total score is $1^2+2^2+2^2+1^2=10$. 2. $q={0, 1, 3, 6}$, the total score is $1^2+2^2+3^2=14$. 3. $q={0, 1, 5, 6}$, the total score is $1^2+0+1^2=2$. 4. $q={0, 1, 6}$, the total score is $1^2+0=1$. 5. $q={0, 3, 5, 6}$, the total score is $3^2+2^2+1^2=14$. 6. $q={0, 3, 6}$, the total score is $3^2+3^2=18$. 7. $q={0, 5, 6}$, the total score is $0+1^2=1$. 8. $q={0, 6}$, the total score is $0$.

The sum of them is $10+14+2+1+14+18+1+0=60$.