C1. Сходящийся массив (простая версия)
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это — упрощенная версия задачи. Единственное различие в том, что в данной версии $$$q = 1$$$. Вы можете взламывать другие решения, только если решены обе версии задачи.

Рассмотрим процесс, проходящий на массивах $$$a$$$ и $$$b$$$ длины $$$n$$$ и $$$n-1$$$ соответственно.

Процесс — это бесконечная последовательность действий. Каждое действие имеет следующий вид:

  • Сначала выберем случайное целое число $$$i$$$ ($$$1 \le i \le n-1$$$).
  • Теперь одновременно присвоим $$$a_i = \min\left(a_i, \frac{a_i+a_{i+1}-b_i}{2}\right)$$$ и $$$a_{i+1} = \max\left(a_{i+1}, \frac{a_i+a_{i+1}+b_i}{2}\right)$$$ без округлений (то есть значения могут перестать быть целыми).
Пример такой операции представлен в заметках.

Можно доказать, что массив $$$a$$$ сходится, т. е. для каждого $$$i$$$ существует предел, к которому $$$a_i$$$ сходится. Пусть функция $$$F(a, b)$$$ возвращает значение, к которому сходится $$$a_1$$$, в результате процесса на массивах $$$a$$$ и $$$b$$$.

Вам задан массив $$$b$$$, но не массив $$$a$$$. Однако вам задан третий массив $$$c$$$. Назовем массив $$$a$$$ хорошим, если он состоит из целых чисел и удовлетворяет неравенству $$$0 \leq a_i \leq c_i$$$ для всех $$$1 \leq i \leq n$$$.

Ваша задача — посчитать количество хороших массивов $$$a$$$, для которых $$$F(a, b) \geq x$$$, для $$$q$$$ значений $$$x$$$. Так как ответ может быть слишком большим, выведите его по модулю $$$10^9+7$$$.

Входные данные

В первой строке задано одно целое число $$$n$$$ ($$$2 \le n \le 100$$$).

Во второй строке заданы $$$n$$$ целых чисел $$$c_1, c_2 \ldots, c_n$$$ ($$$0 \le c_i \le 100$$$).

В третьей строке заданы $$$n-1$$$ целых чисел $$$b_1, b_2, \ldots, b_{n-1}$$$ ($$$0 \le b_i \le 100$$$).

В четвертой строке задано одно целое число $$$q$$$ ($$$q=1$$$).

В пятой строке заданы $$$q$$$ целых чисел $$$x_1, x_2, \ldots, x_q$$$ ($$$-10^5 \le x_i \le 10^5$$$).

Выходные данные

Выведите $$$q$$$ целых чисел, где $$$i$$$-е число — ответ на $$$i$$$-й запрос, т. е. количество хороших массивов $$$a$$$ с $$$F(a, b) \geq x_i$$$ по модулю $$$10^9+7$$$.

Пример
Входные данные
3
2 3 4
2 1
1
-1
Выходные данные
56
Примечание

Объяснение далее предполагает, что $$$b = [2, 1]$$$ и $$$c=[2, 3, 4]$$$ (как в примере).

Примеры массивов $$$a$$$, которые не являются хорошими:

  • $$$a = [3, 2, 3]$$$ не является хорошим, потому что $$$a_1 > c_1$$$;
  • $$$a = [0, -1, 3]$$$ не является хорошим, потому что $$$a_2 < 0$$$.

Один из возможных хороших массивов $$$a$$$ — это $$$[0, 2, 4]$$$. Можно показать, что ни одна операция его не изменит, а потому $$$F(a, b) = a_1 = 0$$$.

Другой возможных хороший массив $$$a$$$ — это $$$[0, 1, 4]$$$. За одну операцию с $$$i = 1$$$ мы присваиваем $$$a_1 = \min(\frac{0+1-2}{2}, 0)$$$ и $$$a_2 = \max(\frac{0+1+2}{2}, 1)$$$. То есть, после одной операции с $$$i = 1$$$, $$$a$$$ становится равен $$$[-\frac{1}{2}, \frac{3}{2}, 4]$$$. Можно показать, что далее ни одна операция не изменит массив, а потому $$$F(a, b) = -\frac{1}{2}$$$.