Order-Preserving Partition

시간 제한2초메모리 제한512 MB

요약

순열을 네 개의 연속된 비어 있지 않은 구간으로 나눌 때, 각 구간의 값이 연속 정수가 되고 구간 최솟값의 순서가 주어진 순위 순열과 일치하는 분할의 수를 센다.

난이도: 보통10점 중 7점
유형: 배열, 누적 합, 조합론, 구현
정답자: 아직 제출이 없습니다

문제

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

예제 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

예상 출력

0
84