The company KDH conducts $N$ meetings every day. The meetings are numbered from $0$ to $N - 1$, and for every $0 \le i \le N - 1$, meeting $i$ starts at time $S[i]$ and ends at time $E[i]$.

KDH has a special way of holding meetings. Two different meetings $i$ and $j$ held on a certain day are called "related" on that day if at least one of the following conditions is satisfied: There exists a time when both meetings are held simultaneously. There exists a meeting $k$ held on that day that is related to both meetings simultaneously.

If two meetings $i$ and $j$ are not related to each other, they are called "unrelated" on that day.

When KDH holds meetings every day, it assigns each meeting to a specific meeting room. In this process, unrelated meetings on that day must not be assigned to the same meeting room. KDH will choose an assignment method that minimizes the number of required meeting rooms among all methods satisfying this condition. Let the minimum number of meeting rooms required for such an assignment be the "cost" of the meetings.

KDH has decided to reduce the number of meetings to just one because it believes that too many resources are being wasted on the current meetings. To achieve this, KDH repeats the following task every day for $N - 1$ days: Choose one meeting that has not been canceled yet. Permanently cancel the chosen meeting from that day onwards. * Conduct all meetings that have not been canceled.

When this process is finished, all meetings except for one are canceled. It does not matter which meeting remains at the end.

To further reduce costs, KDH wants to choose a method among several possibilities such that the sum of the costs required on each day over the $N - 1$ days is minimized. You need to find how many such methods exist for KDH. Two methods are considered the same if the meetings chosen to be canceled on each day are all the same: specifically, if the meetings chosen to be canceled over the $N - 1$ days are all the same, it is considered the same case even if the methods of assigning the remaining meetings to rooms are different. However, since the number of methods can be very large, you must find the remainder when divided by the prime $1\,000\,000\,007$.

Implementation Details

You must implement the following function:

int count_removals(vector<int> S, vector<int> E)

• $S, E$: Integer arrays of size $N$. For all $0 \le i \le N - 1$, meeting $i$ starts at time $S[i]$ and ends at time $E[i]$.
• This function must return the number of ways to decide which meeting to cancel each day to minimize the sum of costs required on each day over the $N - 1$ days, modulo $1\,000\,000\,007$.

You must not execute input/output functions in any part of your submitted source code.

Constraints

• $2 \le N \le 2\,000$
• For all $0 \le i \le N - 1$, $1 \le S[i] < E[i] \le 2N$
• For all $0 \le i < j \le N - 1$, $S[i] \neq S[j]$, $S[i] \neq E[j]$, $E[i] \neq S[j]$, $E[i] \neq E[j]$

Subtasks

1. (3 points)
   • $N \le 10$
   • $S[0] = 1, E[0] = 2N$
2. (8 points)
   • $N \le 20$
3. (30 points)
   • $N \le 300$
4. (12 points)
   • At most 2 meetings are held at any given time.
5. (12 points)
   • For all $0 \le i, j \le N - 1$ where $i \neq j$, there is no pair $i, j$ satisfying $S[i] < S[j] < E[i] < E[j]$.
6. (10 points)
   • For all $0 \le i, j \le N - 1$ where $i \neq j$, there is no pair $i, j$ satisfying $S[i] < S[j] < E[j] < E[i]$.
7. (25 points)
   • No additional constraints.

Examples

Input 1

count_removals([1, 3, 5, 7], [2, 4, 6, 8])

Output 1

24

Input 2

count_removals([1, 2, 4, 6, 8, 10, 12, 14, 16, 18], [5, 3, 7, 11, 9, 15, 13, 20, 17, 19])

Output 2

13280

Input 3

count_removals([1, 2, 3, 5, 6, 10, 11, 12, 14, 18], [20, 9, 4, 8, 7, 17, 16, 13, 15, 19])

Output 3

845040

Input 4

count_removals([1, 2, 3, 4, 6, 7, 8, 11, 13, 15], [5, 9, 10, 12, 14, 16, 17, 18, 19, 20])

Output 4

1797408

Input 5

count_removals([12, 5, 10, 2, 4, 17, 8, 1, 14, 9], [16, 7, 19, 3, 6, 20, 11, 15, 18, 13])

Output 5

647760

Note

The sample grader receives input in the following format: Line 1: $N$ Line $2 + i$ ($0 \le i \le N - 1$): $S[i] \ E[i]$

The sample grader outputs the following: * Line 1: The value returned by the function count_removals

Note that the sample grader may differ from the grader used in actual grading.