题解

题面描述

给定三个长度为 $n$ 的数组：

• $a_i$ 表示第 $i$ 个网页的访问量
• $b_i$ 表示第 $i$ 个网页的维护成本
• $c_i$ 表示第 $i$ 个网页的系数

对于第 $i$ 个网页，我们定义

题目内容

小红开发了一个属于自己的网站，为了验证自己的网站中的哪个网页受大多数人喜欢，她统计了网站中各网页的访问量。第 $i$ 个网页的访问量记为 $a_i$ ，$a_i$ 越大说明此网页越受欢迎。然而，维护网站的成本也不小，第 $i$ 个网页的维护成本记为 $b_i$，$b_i$ 越大说明此网页越难维护。

对于第 $i$ 个网页，我们定义，当网页的访问量与维护成本之差满足 $a_i-b_i > c_i$ 时，该网页被判定为受欢迎；否则判定为不受欢迎。

现在小红准备随机选定一个连续子区间 $[l,r] (1 ≤l≤r≤n)$，如果区间中受欢迎的网页数量大于不受欢迎的网页数量，则小红认为此网站是受欢迎的，否则是不受欢迎的。

小红想要知道，依据这种方式，有多大的概率能够判定得到，自己的网站是受欢迎的?为了避免精度问题，请将答案对 $(10^9+7)$ 取模后输出。

提示:本题中，在进行除法的取模时，即计算 $(p×q^{-1}$ $mod$ $M)$ ，其中 $q^{-1}$ 可以使用公式 $(q^{M-2}$ $mod$ $M)$ 得到：例如，在计算 $\frac 54$ $mod$ $M$时，根据公式 $4^{-1}=(4^{M-2}$ $mod$ $M)=250$ $000$ $002$，得到 $(p×q^{-1}$ $mod$ $M)=5×250$ $000$ $002$ $mod$ $M= 250$ $000$ $003$ 。

输入描述

第一行输入一个整数 $n(1 ≤ n ≤ 10^5)$ 表示网页的数量。

第二行输入 $n$ 个整数 $a_i(1 ≤ a_i< 10^9)$表示第 $i$ 个网页的访问量。

第三行输入 $n$ 个整数 $b_i(1 ≤ b_i< 10^9)$ 表示第 $i$ 个网页的维护成本。

第四行输入 $n$ 个整数 $c_i (1 ≤ c_i < 10^9)$ 表示第 $i$ 个网灭页系数。

输出描述

可以证明答案可以表示为一个不可约分数$\frac qp$，为了避免精度问题，请直接输出整数$(p×q^{-1}$ $mod$ $M)$ 作为答案，其中 $M =(10^9+7)$，$q^{-1}$ 是满足 $q×q^{-1}≡1$($mod$ $M$)的整数。

更具体地，你需要找到一个整数 $x ∈[0,M)$ 满足 $x×q$ 对 $M$ 取模等于 $p$，您可以查看样例解释得到更具体的说明。

样例1

输入

3
3 2 6
1 2 3
1 1 2

输出

500000004

说明

第一个网页是 $a_1-b_1=3-1=2>1$，受欢迎

第二个网页是 $a_2-b_2=2-2=0<1$，不受欢迎

第三个网页是 $a_3-b_3=6-3=3>2$，受欢迎。

如果随机选择区间，一共有六种不同的选法，分别是：

选择区间 $[1,1]$，唯一 一个网页是受欢迎的，所以网站也受欢迎；

选择区间 $[1,2]$，一个网页受欢迎、一个网页不受欢迎，所以网站不受欢迎；

选择区间 $[1,3]$，两个网页受欢迎、一个网页不受欢迎，所以网站受欢迎；

选择区间 $[2,2]$，唯一 一个网页不受欢迎，所以网站不受欢迎；

选择区间 $[2,3]$，一个网页受欢迎、一个网页不受欢迎，所以网站不受欢迎；

选择区间 $[3,3]$，唯一 一个网页是受欢迎的，所以网站也受欢迎。

这样，网站有$\frac 36$ 的概率是受欢迎的。我们能够找到，

$500$ $000$ $004$ $× 2=1$ $000$ $000$ $008$ ，对 $10^9+7$ 取后恰好等于分子 $1$，所以 $500$ $000$ $004$ 是需要输出的答案。