You are given three integers $l$, $r$, and $n$. You are also given an array of integers $a[1], a[2], ..., a[n-1]$ of size $n-1$.

Determine the possible number of ways of selecting $n$ integers $x_{1}, x_{2}, ..., x_{n}$ from the range $[l, r]$ such that the selected integers are in strictly increasing order (from left to right).

Note

•  $x_{i+1} - x_i \ge a[i] \space \forall \space 1 \le i \lt n$
• Output must be printed as modulo $1000000007$

Input format

• First line: Three space-separated integers $l$, $r$, and $n$
• Second-line: $n-1$ space-separated integers $a[1 .. n-1]$

Output format

Print the possible number of ways of selecting $n$ integers $x_1, x_2, ..., x_n$.

Constraints

$-10^6 \le l \le r \le 10^6 \\ 2 \le n \le 10^6 \\ 0 \le a[i] \le 10^9$