Кількість розв'язків рівняння

Обмеження: 4 сек., 256 МіБ

Зеник уміє шукати кількість цілочислових розв’язків рівняння $x_1 + x_2 + \ldots + x_n = k$, що задовольняють обмеження $0 \le x_i \le a_i$ для кожного $i$.

Марічка вважає цю задачу легкою та ускладнила її.

Задано масив $a$ з $n$ елементів.

Є запити двох типів:

• 1 $i$ $v$ — змінити $a_i$ на $v$

• 2 $k$ — знайти відповідь на задачу, описану в першому абзаці, для заданого $k$ за модулем простого числа $10^9+7$.

Поки Зеник чухає потилицю, опрацюйте запити Марічки.

Вхідні дані

Перший рядок містить ціле число $n$ — кількість змінних у рівнянні.

У другому рядку записано $n$ цілих чисел $a_i$ — обмеження на $x_i$.

Третій рядок містить ціле число $q$ — кількість запитів.

Кожен з наступних $q$ рядків описує запит у форматі, зазначеному в умові.

Вихідні дані

Для кожного запиту другого типу в окремому рядку виведіть ціле число — кількість цілочислових розв’язків рівняння за модулем $10^9+7$.

Обмеження

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

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
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