Converging Array (Easy Version)

题意翻译

现在有长度为 $n$ 的数组 $a$ 和长度为 $n-1$ 的数组 $b$，进行无穷次如下过程直至 $a$ 数组收敛： * 选择一个数 $i$（$1\leq i<n$）。 * 同时使 $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)$（没有取整） 定义 $F(a,b)$ 为操作完成后 $a_1$ 的值。 给定数组 $b$ 和长度为 $n$ 的数组 $c$，你需要保证 $0\leq a_i\leq c_i$。 有 $q$ 组询问，每次问使 $F(a,b)\geq x_i$ 的数组 $a$ 有多少个。答案对 $10^9+7$ 取模。

题目描述

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

输入输出格式

输入格式

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

输入输出样例

输入样例 #1

3
2 3 4
2 1
1
-1

输出样例 #1

56

说明

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