Bobo 有两个排列：$P = \{p_1, p_2, \dots, p_n\}$ 和 $Q = \{q_1, q_2, q_3, q_4\}$。他想将 $P$ 分成四个非空且连续的部分，要求满足以下条件：

• 每一部分中的数字可以重新排列形成一个值域区间：即一个递增序列，其中每个元素比前一个元素恰好大 1。
• 对于所有 $1 \le i < j \le 4$，满足 $(s_i - s_j) \cdot (q_i - q_j) > 0$，其中 $s_i$ 是第 $i$ 部分中的最小值。

Bobo 想知道满足条件的划分方案数。由于方案数可能非常大，你只需要输出答案对 $(10^9 + 7)$ 取模的结果。

输入格式

输入包含零个或多个测试用例，以文件结束符（EOF）终止。对于每个测试用例：

第一行包含一个整数 $n$，表示第一个排列的长度（$4 \le n \le 10^6$）。 第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$。 第三行包含四个整数 $q_1, q_2, q_3, q_4$。

保证所有 $n$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，输出一个整数表示答案。

样例

样例输入 1

10
2 1 4 3 10 9 8 7 5 6
2 4 1 3

样例输出 1

0

样例输入 2

10
1 2 3 4 5 6 7 8 9 10
1 2 3 4

样例输出 2

84