Bajtek 刚刚参加了算法与数据结构口试。他复习得并不充分，表现得不太理想。几分钟交谈后，失望的教授决定给这个男孩最后一次机会。

“孩子，你至少知道什么是 BST（二叉搜索树）吧？”教授问道。

Bajtek 嘴角微微上扬，因为他在课堂打盹时，确实记下了一些理论知识。

“是的，大小为 $n$ 的 BST 是一棵有根树，其顶点编号为 $1$ 到 $n$。每个顶点最多有两个子节点：最多一个左儿子和最多一个右儿子。此外，每个顶点的编号必须大于其左子树中所有顶点的编号，且小于其右子树中所有顶点的编号。”Bajtek 从潜意识深处挖掘出答案。

“很好。我们来看看你是否还记得如何对它们进行旋转操作。”教授说完，站起身走向黑板。

Bajtek 吓出了一身冷汗。他瞬间失去了自信，因为他不记得旋转操作的具体运作方式了（大概在讲课的那一刻他正好翻了个身，盖过了教授的声音）。考官在黑板上画了两棵大小相同的 BST，并要求 Bajtek 通过正确的旋转将第一棵树转换为第二棵。

Bajtek 思考了一会儿，假设左旋转是选择某个顶点 $v$ 及其右儿子 $w$，并使 $w$ 成为 $v$ 的父亲。Bajtek 的直觉由以下伪代码形式化：

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

同样，Bajtek 对右旋转的理解是，其中 $w$ 是顶点 $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

然而，男孩很快注意到有些不对劲。如果在左旋转过程中，顶点 $w$ 有任何左子树，它将会丢失！在右旋转过程中，顶点 $w$ 的右子树也可能发生同样的情况。

“快点，孩子，不止你一个人想通过这场考试。”不耐烦的教授催促道。

由于没有太多时间思考，Bajtek 假设只有当那些有问题的子树为空时，他才能执行旋转，即不会丢失任何顶点，且树保持连通。

为了尽快结束折磨，他决定执行最少次数的旋转，将第一棵树转换为第二棵。你能判断这是否可行吗？如果可行，他需要执行多少次旋转？由于这个数字可能很大，你只需要输出它对 $10^9 + 7$ 取模后的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 5 \cdot 10^5$)，表示教授所画树的大小。

接下来的两行描述了这两棵树。每棵树的描述由 $n$ 个整数 $a_1, a_2, \dots, a_n$ 组成 ($-1 \le a_i \le n, a_i \neq 0$)；值 $a_i \ge 1$ 表示第 $i$ 个顶点的父亲是顶点 $a_i$；值 $a_i = -1$ 表示第 $i$ 个顶点是整棵树的根。

你可以假设这两棵树都是合法的 BST，即它们没有环，只有一个根，且每个顶点最多有一个比自己小的儿子和一个比自己大的儿子（并且满足顶点与其子树的比较条件）。

输出格式

输出一个整数，表示将第一棵树转换为第二棵树所需的最少旋转次数（按 Bajtek 的理解）对 $10^9 + 7$ 取模后的结果，如果无法转换，则输出 $-1$。

样例

输入 1

4
3 1 -1 3
2 -1 4 2

输出 1

3

输入 2

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

输出 2

7

说明 1

下图展示了转换树所需的最少旋转次数：