Bajtek has just started an oral exam on Algorithms and Data Structures. He hasn't studied for it for very long, so he isn't doing very well. After a few minutes of conversation, the devastated lecturer decided to give the boy one last chance.

"Do you at least know, boy, what BST trees are?" asked the professor.

Bajtek smiled to himself upon hearing this, as during his nap in the lecture, some theory had stuck in his memory.

"Yes, a BST tree of size $n$ is a rooted tree whose vertices are numbered with integers from 1 to $n$. Each vertex can have at most two children; it can have a left (at most one) child and a right (at most one) child. Additionally, the number of each vertex must be greater than the numbers of all vertices in its left subtree and smaller than the numbers of all vertices in its right subtree," Bajtek replied, reaching into the depths of his subconscious.

"Good. Let's see if you remember how to perform rotations on them," replied the professor, who had been sitting until now, after which he stood up and headed toward the board.

Cold sweat poured over Bajtek. He instantly lost his confidence, as he didn't remember exactly how rotations work (he was probably turning over in his sleep at that moment in the lecture, and that must have drowned out the lecturer's words). The examiner drew two BST trees of the same size on the board and ordered Bajtek to transform the first one into the second using correct rotations.

Bajtek thought for a moment and assumed that a left rotation means choosing a certain vertex $v$ and its right child $w$, and making $w$ the parent of $v$. Bajtek's intuition is formalized by the following pseudocode:

if v.Ojciec != null then
if v.Ojciec.PrawySyn == v then
v.Ojciec.PrawySyn := w
else
v.Ojciec.LewySyn := w
w.Ojciec := v.Ojciec
v.Ojciec := w
w.LewySyn := v
v.PrawySyn := null

Similarly, Bajtek understands a right rotation, where $w$ is the left child of vertex $v$:

if v.Ojciec != null then
if v.Ojciec.PrawySyn == v then
v.Ojciec.PrawySyn := w
else
v.Ojciec.LewySyn := w
w.Ojciec := v.Ojciec
v.Ojciec := w
w.PrawySyn := v
v.LewySyn := null

However, the boy quickly noticed that something was wrong. If during a left rotation vertex $w$ had any left subtree, it would be lost! The same could happen with a potential right subtree of vertex $w$ during a right rotation.

"Hurry up, boy, you're not the only one who would like to pass this exam," the impatient professor urged him.

Not having much time to think, Bajtek assumed that a rotation can only be performed when that problematic subtree is empty, i.e., when it does not lose any vertex, and the tree remains connected.

Wanting to end his ordeal as quickly as possible, he decided that he would perform the minimum number of rotations that would allow him to transform the first tree into the second. Can you determine if this is possible, and if so, how many rotations he will have to perform? Since this number can be quite large, it is enough to provide its remainder when divided by $10^9 + 7$.

Input

The first line of input contains a single integer $n$ ($1 \le n \le 5 \cdot 10^5$) representing the size of the trees drawn by the professor.

The next two lines contain descriptions of these trees. The description of a tree consists of a sequence of $n$ integers $a_1, a_2, \dots, a_n$ ($-1 \le a_i \le n, a_i \neq 0$); a value $a_i \ge 1$ means that the parent of the $i$-th vertex is vertex $a_i$; a value $a_i = -1$ means that the $i$-th vertex is the root of the entire tree.

You can assume that both trees are valid BST trees, i.e., there are no cycles in them, there is exactly one root, and each vertex has at most one child smaller than itself and one child larger than itself (and the condition regarding comparing a vertex with its subtrees holds).

Output

The output should contain a single integer representing the remainder when divided by $10^9 + 7$ of the minimum possible number of rotations (in Bajtek's understanding) needed to transform the first tree into the second, or $-1$ if such a transformation is not possible.

Examples

Input 1

4
3 1 -1 3
2 -1 4 2

Output 1

3

Input 2

8
2 4 2 7 4 5 -1 7
2 3 6 5 3 -1 6 7

Output 2

7

Note

Explanation of the first example: The figure below shows the minimum number of rotations transforming the trees: