시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 1 1 100.000%

문제

Bobo has two permutations: $P = \{p_1, p_2, \ldots, p_n\}$ and $Q = \{q_1, q_2, q_3, q_4\}$. He would like to partition $P$ into four non-empty and contiguous parts in such a manner that:

  • The numbers in each part can be rearranged to form an interval of values: an increasing sequence where each element is greater than the previous by exactly one.
  • For all $1 \leq i < j \leq 4$, $(s_i - s_j) \cdot (q_i - q_j) > 0$ where $s_i$ is the minimum value in the $i$-th part.

Bobo wants to know the number of such partitions. As the number may be very large, you just need to print the answer modulo $(10^9 + 7)$.

입력

The input contains zero or more test cases, and is terminated by end-of-file. For each test case:

The first line contains an integer $n$, the length of the first permutation $(4 \leq n \leq 10^6)$.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$.

The third line contains four integers $q_1, q_2, q_3, q_4$.

It is guaranteed that the sum of all $n$ does not exceed $10^6$.

출력

For each test case, output an integer denoting the answer.

예제 입력 1

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

예제 출력 1

0
84