U230162 Jumping steps

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. Liu can't jump onto them. The broken steps are $p_1,p_2,\cdots,p_m$ ($p_i

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$.

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

Explanation of example #2: 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$.