After holding the summer courses of Computer Olympiad, it is time to hold the final practical exams.

In this summer period
n
n scholars were studying and therefore also in final exams
n
n scholars will study knowledge. in the exam hall as well
n
n computers are prepared for them who are placed around a circular table and in clockwise order with numbers
1
1 to
n
n are numbered.

Amirmohammed, who very much wanted his work to be available in the final exams, undertook the important task of identifying the seats of the scholars in the first exam. Therefore, each scholar is given a number of
1
1 to
n
n attributed that his computer number identified him. In other words, an array
a
a to length
n
n identified that
a
i
a
i
​
 Student's computer number
i
I was diagnosed during the test.

But the case was not that simple... due to some technical problems, the array
a
a contained a number of duplicate members! That is, some computer scholars were attributed the same. Amirmohammed, who had found out about this incident before the exam started, shared the problem with Majid.

Majid decided that the process of sitting the scholars in the hall should be in such a way that they first stand behind the exam hall in a line; Then enter the exam hall from the beginning of the queue. Whenever a scholar enters the exam hall and sees that the scholar is sitting behind the computer he wants, he should go to the next computer (clockwise). The scholar should continue this work until he reaches an empty computer and sits at that computer. In other words, a scholar
i
I am behind the first computer after
a
i
a
i
​
 (Including yourself
a
i
a
i
​
 ) sits so that no other scholar is sitting behind him when he enters the hall. After each scholar sits behind a computer, the next person in line enters the hall.

In this way, the scholars were able to sit at their computers without any particular problem and the exam was held smoothly. During the exam, Majid explained the incident to Shayan. Shayan, who is severely suffering from the lack of questions for practical exams, decided to raise a question about this story! Worth the array
b
b to length
n
Define n:
b
i
b
i
​
 The number of the computer that the student
i
Iam is sitting behind it. The interesting question was that if we have the array
a
a and
b
b, the students can form a queue behind the exam hall door in several ways that after entering the hall, the student
i
I am behind the computer
b
i
b
i
​
 be sitting

Shayan, who has to prepare other questions, wants you to solve this question for him!

input
In the first line of the input number
n
n has arrived.
in
i
The next row, two numbers in order
a
i
a
i
​
 and
b
i
b
i
​
 has come
It is guaranteed that the array of
b
b is a permutation.

1
≤
n
≤
1
0
5
1≤n≤10
5

1
≤
a
i
,
b
i
≤
n
1≤a
i
​
 ,b
i
​
 ≤n
output
In the only output line, the remaining number of valid sequences is measured
1
0
9
+
7
10
9
 Output +7.

Sub-problems
Constraints score subproblem
1 7
n
≤
10
n≤10
2 8 There is at most one optimal state.
3 25
∀
1
≤
i
≤
n
:
b
i
-
a
i
≡
0

O
r

1
(
m
O
d
n
)
∀
1≤i≤n
​
 :b
i
​
 -a
i
​
 ≡0 or 1(modn)
4 60 without additional restrictions
Example
Sample entry 1
3
2 2
3 3
2 1
Plain text
Sample output 1
2
Plain text
Sample input 2
13
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
Plain text
Sample output 2
227020758
Plain text
Sample entry 3
4
4 4
3 1
1 2
2 3
Plain text
Sample output 3
0   c++