题目描述

给定两个长度为 $N$ 的自然数序列：

$$V_1,V_2,\ldots,V_N$$

和

$$E_1,E_2,\ldots,E_N.$$

对于每一段连续子序列 $[l,r]$，若它的两个端点满足：

$$E_l=E_r,$$

则该子序列会对答案贡献：

$$\max(V_l,V_{l+1},\ldots,V_r).$$

请计算所有满足 $1\le l\le r\le N$ 且 $E_l=E_r$ 的连续子序列的贡献和，对

$$1\,000\,000\,007$$

取模输出。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个自然数，表示序列 $V$。

第三行包含 $N$ 个自然数，表示序列 $E$。

输出格式

输出一行一个整数，表示所求答案对 $1\,000\,000\,007$ 取模后的结果。

数据范围与约定

• $1\le N\le 3\times 10^5$；
• $1\le V_i,E_i\le 10^9$；
• 连续子序列指下标连续的一段。

子任务

子任务	分值	限制
1	8	$N\le 2000$
2	11	对所有 $1\le i\le N$，$E_i=1$
3	12	对所有 $1\le i\le N$，$E_i\le 20$
4		对所有 $1\le i\le N$，$V_i\le 20$
5	19	$N\le 5\times 10^4$
6	38	无额外限制

样例

5
5 29 3 28 30
9 8 9 9 8

211

样例解释

贡献答案的子序列必须满足两端的 $E$ 值相等。

本例中，满足条件的区间及其最大值为：

$$(1,1,5),\ (1,3,29),\ (1,4,29),\ (2,2,29),\ (2,5,30),$$$$(3,3,3),\ (3,4,28),\ (4,4,28),\ (5,5,30).$$

这些最大值之和为：

$$5+29+29+29+30+3+28+28+30=211.$$