Number of Solutions of the Equation

Limits: 4 sec., 256 MiB

Zenyk can find number of integer solutions of the equation \(x_1 + x_2 + \ldots + x_n = k\), which satisfy the constraints \(0 \le x_i \le a_i\) for each \(i\).

Marichka finds this problem easy and complicated it.

Given an array \(a\) of \(n\) elements.

There are queries of two types:

• 1 \(i\) \(v\) — change \(a_i\) to \(v\)

• 2 \(k\) — find the answer to the problem described in the first paragraph for given \(k\) modulo the prime number \(10^9+7\).

While Zenyk scratches the back of his head, process Marichka’s queries.

Input

The first line contains an integer \(n\) – the number of variables in the equation.

The second line contains \(n\) integers \(a_i\) – the constraints on \(x_i\).

The third line contains an integer \(q\) – the number of queries.

Each of the next \(q\) lines describes a query in format specified in the statement.

Output

For each query of the second type print an integer in the separate line – number of integer solutions of the equation modulo \(10^9+7\).

Constraints

\(1 \le n \le 10^3\),

\(1 \le q \le 10^5\),

\(1 \le i \le n\),

\(0 \le a_i, v, k \le 10^3\).

Samples

Input (stdin) сopy	Output (stdout) сopy
2 3 3 10 2 3 2 4 1 1 0 2 3 1 1 1 2 3 1 1 2 2 3 1 1 3 2 3	4 3 1 2 3 4