Problem: This 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 ≤ i ≤ 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). 

See notes for an example of an operation.

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 ≤ a_i ≤ c_i for 1 ≤ i ≤ n.

Your task is to count the number of good arrays a where F(a, b) ≥ 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 ≤ n ≤ 100).

The second line contains n integers c_1, c_2 …, c_n (0 ≤ c_i ≤ 100).

The third line contains n-1 integers b_1, b_2, …, b_{n-1} (0 ≤ b_i ≤ 100).

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

The fifth line contains q space separated integers x_1, x_2, …, x_q (-10^5 ≤ x_i ≤ 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) ≥ 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((0+1-2)/(2), 0) and a_2 = max((0+1+2)/(2), 1). So, after a single operation with i = 1, a becomes equal to [-1/2, 3/2, 4]. We can show that no operation has any effect on this array, so F(a, b) = -1/2.

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class C {
	
	static final long mod=1_000_000_007;
	static int[] minPrefixSumForPos;
	static int[] aMaxes;
	static long[][] dp;

	public static void main(String[] args) {
		FastScanner fs=new FastScanner();
		dp=new long[101][100_01];
		for (int i=0; i<dp.length; i++) Arrays.fill(dp[i], -1);
		int n=fs.nextInt();
		aMaxes=fs.readArray(n);
		int[] diffs=fs.readArray(n-1);
		int nQueries=fs.nextInt();
		
		int minStart=fs.nextInt();
		minPrefixSumForPos=new int[n];
		minPrefixSumForPos[0]=minStart;
		int lastValue=minStart;
		for (int i=1; i<n; i++) {
			lastValue+=diffs[i-1];
			minPrefixSumForPos[i]=minPrefixSumForPos[i-1]+lastValue;
		}
		
		long ans=dp(0, 0);
		System.out.println(ans);
	}
	
	//100 positions, 10_000 prefix sums
	static long dp(int position, int prefixSum) {
		if (position == aMaxes.length) return 1;
		if (dp[position][prefixSum]!=-1) return dp[position][prefixSum];
		
		int biggestPlace=aMaxes[position];
		//place between 0 and biggestPlace;
		int smallestPlace=Math.max(0, minPrefixSumForPos[position]-prefixSum);
		if (smallestPlace>biggestPlace) return 0;
	
		//TODO: make this part O(1);
		long ans=0;
		for (int toPlace=smallestPlace; toPlace<=biggestPlace; toPlace++) {
			ans=add(ans, dp(position+1, prefixSum+toPlace));
		}
		return dp[position][prefixSum]=ans;
	}

	static void sort(int[] a) {
		ArrayList<Integer> l=new ArrayList<>();
		for (int i:a) l.add(i);
		Collections.sort(l);
		for (int i=0; i<a.length; i++) a[i]=l.get(i);
	}
	
	static long add(long a, long b) {
		return ((a+b)%mod+mod)%mod;
	}
	
	static long mul(long a, long b) {
		return a*b%mod;
	}
	
	static long pow(long base, long exp) {
		if (exp==0) return 1;
		long half=pow(base, exp/2);
		if (exp%2==0) return mul(half, half);
		else return mul(half, mul(half, base));
	}
	
	static long inv(long x) {
		return pow(x, mod-2);
	}
	
	static long[] facts=new long[1_000_00];
	static long[] factsInv=new long[1_000_00];
	
	static void precomp() {
		facts[0]=1;
		for (int i=1; i<facts.length; i++) facts[i]=mul(facts[i-1],i);
		for (int i=0; i<factsInv.length; i++) factsInv[i]=inv(facts[i]);
	}
	
	static long nCk(int n, int k) {
		return mul(facts[n], mul(factsInv[k], factsInv[n-k]));
	}
	
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}

	
}