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\)