给你两个整数序列$a$和$b(b_i \neq 0)$ 且 $|b_i| \leq 10^9$ 。数组$a$保证非降。

一个子序列$a[l:r]$的贡献定义如下。

• 如果 $sum_{j = l}^{r} b_j\neq 0$，那么代价就没有（不会出现此类询问，就是说询问中 $l, r$ 保证 $sum_{j = l}^{r} b_j = 0$ ）。
• 此外
  • 建一个有$r-l+1$个顶点的二分图，从$l$到$r$编号，$b_i \lt 0$的顶点在左边，$b_i \gt 0$的顶点在右边。对于每个$i, j$，若$l\le i, j\le r$，$b_i<0$且$b_j>0$，则建一条从$i$到$j$的边，容量无限，费用为$|a_i-a_j|$。
  • 再添加源$S$和汇$T$。
  • 对于每个$i$，若$l\le i\le r$且$b_i<0$，则建一条从$S$到$i$的边，费用为$0$，容量为$|b_i|$。
  • 对于每个$i$，若$l\le i\le r$且$b_i>0$，则建一条从$i$到$T$的边，费用为$0$，容量为$|b_i|$。
  • $a[l:r]$的贡献就是从$S$到$T$的 $\mathrm{MCMF}$。

$q$次查询，每次给出两个整数$l$和$r$，求出$a[l:r]$的贡献对$10^9 + 7$取模的结果。

markdown 源码

给你两个整数序列$a$和$b(b_i \neq 0)$ 且 $|b_i| \leq 10^9$ 。数组$a$保证非降。   

一个子序列$a[l:r]$的贡献定义如下。   

- 如果 $sum_{j = l}^{r} b_j\neq 0$，那么代价就没有（不会出现此类询问，就是说询问中 $l, r$ 保证 $sum_{j = l}^{r} b_j = 0$ ）。   
- 此外
  - 建一个有$r-l+1$个顶点的二分图，从$l$到$r$编号，$b_i \lt 0$的顶点在左边，$b_i \gt 0$的顶点在右边。对于每个$i, j$，若$l\le i, j\le r$，$b_i<0$且$b_j>0$，则建一条从$i$到$j$的边，容量无限，费用为$|a_i-a_j|$。
  - 再添加源$S$和汇$T$。
  - 对于每个$i$，若$l\le i\le r$且$b_i<0$，则建一条从$S$到$i$的边，费用为$0$，容量为$|b_i|$。
  - 对于每个$i$，若$l\le i\le r$且$b_i>0$，则建一条从$i$到$T$的边，费用为$0$，容量为$|b_i|$。
  - $a[l:r]$的贡献就是从$S$到$T$的 $\mathrm{MCMF}$。

$q$次查询，每次给出两个整数$l$和$r$，求出$a[l:r]$的贡献对$10^9 + 7$取模的结果。