Gustav 是北欧天体行星飞船 (NCPC) 上的一名宇航员，这是一艘绕火星轨道运行的大型空间站。今天，Gustav 的任务之一是检查船上的安全程序。

该空间站由 $n$ 个模块组成，这些模块排列成一个圆环，使得模块 $i$ 与模块 $i+1$ 相连（对于 $i = 1 \dots n-1$），且模块 $n$ 与模块 $1$ 相连。每个模块 $i$ 都有一个非负整数类型 $a_i$，代表可以在该处找到的设备种类。不同的模块可以具有相同的类型。在紧急情况下，必须重新排列设备，使得每个模块 $i$ 变为类型 $b_i$，其中 $b_1, b_2, \dots, b_n$ 是列表 $a$ 的一个重排。

Gustav 注意到，如果某些模块连接断开，导致空间站分裂成若干独立的部分，那么可能无法执行这种设备重排。他决定通过计算空间站可以被分成两个或更多部分，且仍然能够根据紧急程序重新排列设备的方式数量，来评估遵循安全程序的可能性。

换句话说，你的任务是计算有多少种方式可以将循环列表 $a$ 分割成至少两个非空的连续区间，使得循环列表 $b$ 可以通过重排每个区间内的元素得到。由于这个数字可能非常大，你需要求出其对 $10^9 + 7$ 取模后的余数。

例如，考虑下方的样例 1。这里列表 $a$ 可以被分割为 $[1|223|4]$，表示模块 1 和 2 之间的连接，以及模块 4 和 5 之间的连接被切断。注意，在此分割中，模块 5 和 1 之间的连接保持不变。另一种可能的分割方式是 $[12|2|34]$。

在下方的样例 2 中，将列表 $a$ 分割成至少两个非空部分的唯一方式是将两个模块分开。但这样就无法通过重排各部分来创建列表 $b$。因此，答案为 0。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 10^6$)，表示模块的数量。 第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$)。 第三行包含 $n$ 个整数 $b_1, \dots, b_n$ ($0 \le b_i \le 10^9$)。

保证列表 $b$ 是列表 $a$ 的一个重排。

输出格式

输出一个整数，表示安全分割的数量对 $10^9 + 7$ 取模后的结果。

样例

样例输入 1

5
1 2 2 3 4
4 3 2 2 1

样例输出 1

2

样例输入 2

2
1 2
2 1

样例输出 2

0