Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C1. Converging Array (Easy Version)

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThis is the easy version of the problem. The only difference is that in this version $$$q = 1$$$. You can make hacks only if both versions of the problem are solved.

There is a process that takes place on arrays $$$a$$$ and $$$b$$$ of length $$$n$$$ and length $$$n-1$$$ respectively.

The process is an infinite sequence of operations. Each operation is as follows:

- First, choose a random integer $$$i$$$ ($$$1 \le i \le n-1$$$).
- Then, simultaneously set $$$a_i = \min\left(a_i, \frac{a_i+a_{i+1}-b_i}{2}\right)$$$ and $$$a_{i+1} = \max\left(a_{i+1}, \frac{a_i+a_{i+1}+b_i}{2}\right)$$$ without any rounding (so values may become non-integer).

It can be proven that array $$$a$$$ converges, i. e. for each $$$i$$$ there exists a limit $$$a_i$$$ converges to. Let function $$$F(a, b)$$$ return the value $$$a_1$$$ converges to after a process on $$$a$$$ and $$$b$$$.

You are given array $$$b$$$, but not array $$$a$$$. However, you are given a third array $$$c$$$. Array $$$a$$$ is good if it contains only integers and satisfies $$$0 \leq a_i \leq c_i$$$ for $$$1 \leq i \leq n$$$.

Your task is to count the number of good arrays $$$a$$$ where $$$F(a, b) \geq x$$$ for $$$q$$$ values of $$$x$$$. Since the number of arrays can be very large, print it modulo $$$10^9+7$$$.

Input

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 100$$$).

The second line contains $$$n$$$ integers $$$c_1, c_2 \ldots, c_n$$$ ($$$0 \le c_i \le 100$$$).

The third line contains $$$n-1$$$ integers $$$b_1, b_2, \ldots, b_{n-1}$$$ ($$$0 \le b_i \le 100$$$).

The fourth line contains a single integer $$$q$$$ ($$$q=1$$$).

The fifth line contains $$$q$$$ space separated integers $$$x_1, x_2, \ldots, x_q$$$ ($$$-10^5 \le x_i \le 10^5$$$).

Output

Output $$$q$$$ integers, where the $$$i$$$-th integer is the answer to the $$$i$$$-th query, i. e. the number of good arrays $$$a$$$ where $$$F(a, b) \geq x_i$$$ modulo $$$10^9+7$$$.

Example

Input

3 2 3 4 2 1 1 -1

Output

56

Note

The following explanation assumes $$$b = [2, 1]$$$ and $$$c=[2, 3, 4]$$$ (as in the sample).

Examples of arrays $$$a$$$ that are not good:

- $$$a = [3, 2, 3]$$$ is not good because $$$a_1 > c_1$$$;
- $$$a = [0, -1, 3]$$$ is not good because $$$a_2 < 0$$$.

One possible good array $$$a$$$ is $$$[0, 2, 4]$$$. We can show that no operation has any effect on this array, so $$$F(a, b) = a_1 = 0$$$.

Another possible good array $$$a$$$ is $$$[0, 1, 4]$$$. In a single operation with $$$i = 1$$$, we set $$$a_1 = \min(\frac{0+1-2}{2}, 0)$$$ and $$$a_2 = \max(\frac{0+1+2}{2}, 1)$$$. So, after a single operation with $$$i = 1$$$, $$$a$$$ becomes equal to $$$[-\frac{1}{2}, \frac{3}{2}, 4]$$$. We can show that no operation has any effect on this array, so $$$F(a, b) = -\frac{1}{2}$$$.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/23/2021 05:45:30 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|