Description

"Stitch又在摸鱼，我们去看看他是不是又去玩红警挨虐了。"集训队某位成员说道。

但是这次Stitch没有去玩红警，他选择去玩一些更适合他的智力的游戏，没错，他在拿白纸画鸡蛋。

不幸的是，Stitch玩这个也被发现了，随后这位队员给Stitch出了一个题目。

他拿出了2*n张白纸分别在上边写上了一个数字，这2*n个数字满足有两个1，两个2...两个n。

随后他把这些写过数字白纸分成了两行，每行有n张，且这n张中分别有1,2...n这些数字各一个，也就是这两行分别形成了一个1-n的排列。

现在这位队员想要让Stitch仅通过交换同一列中的数字(指交换白纸位置从而改变数字的上下行关系)确保同一行中没有相同的数字。

这位队员又觉得Stitch做这个可能一天就做完了，不能让他闲着，所以他现在问的是通过以上交换方式最终能有多少种状态满足条件？交换可以无限次进行。

Input Format

第一行输入一个整数$n(n≤10​^5​)$，含义如题面所示。

接下来两行每行输入n个整数满足这n个整数为1-n的一个排列。

Output Format

输出一个整数表示答案，为了防止输出过大超过long long范围，所以请输出答案对1000000007取模后的结果。

4
1 4 2 3
3 2 1 4​

2​

Hint

两种合法的状态分别为:

[1,4,2,3]在第一行，[3,2,1,4]在第二行

[3,2,1,4]在第一行，[1,4,2,3]在第二行