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

Обмеження: 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