Intact Intervals

Gustav는 화성 궤도를 도는 거대한 우주 정거장 NCPC(Nordic Celestial Planetary Craft)의 우주 비행사이다. 오늘 Gustav의 임무 중 하나는 정거장 내부의 안전 절차를 점검하는 것이다.

우주 정거장은 원형으로 배치된 $n$개의 모듈로 이루어져 있으며, 모듈 $i$는 $i = 1 \ldots n-1$에 대해 모듈 $i+1$과 연결되고, 모듈 $n$은 모듈 $1$과 연결된다. 각 모듈 $i$에는 음이 아닌 정수 타입 $a\_i$가 있으며, 이는 그곳에 있는 장비의 종류를 나타낸다. 서로 다른 모듈이 같은 타입을 가질 수도 있다. 비상시에는 각 모듈 $i$가 대신 타입 $b\_i$를 갖도록 장비를 재배치해야 하며, 여기서 $b$는 $a$를 재배열한 것이다.

Gustav는 일부 모듈 간 연결이 끊겨 우주 정거장이 여러 부분으로 나뉘면 이 장비 재배치를 수행하지 못할 수도 있다는 사실을 알아냈다. 그는 비상 절차에 따라 장비를 재배치하는 것이 여전히 가능하도록 우주 정거장을 두 개 이상의 부분으로 분리하는 방법이 몇 가지인지 계산하여, 안전 절차를 지킬 수 있을 가능성을 추정하려 한다.

다시 말해, 원형 리스트 $a$를 적어도 두 개의 비어 있지 않은 연속 구간으로 분할하여, 각 구간 내에서 원소를 재배열함으로써 원형 리스트 $b$를 얻을 수 있는 방법의 수를 세는 것이다. 이 수는 매우 클 수 있으므로 $10^9+7$로 나눈 나머지를 구해야 한다.

예를 들어 아래 Sample Input 1을 보자. 여기서 리스트 $a$는 $[1 | 2 2 3 | 4]$로 분할될 수 있으며, 이는 모듈 $1$과 $2$ 사이의 연결, 그리고 모듈 $4$와 $5$ 사이의 연결이 끊겼음을 나타낸다. 이 분할에서 모듈 $5$와 $1$ 사이의 연결은 그대로 유지된다. $a$가 분할될 수 있는 두 번째 방법은 $[1 2 | 2 | 3 4]$이다.

Sample Input 2에서는 리스트 $a$를 적어도 두 개의 비어 있지 않은 부분으로 나누는 유일한 방법이 두 모듈을 분리하는 것이다. 하지만 그렇게 하면 부분들을 재배열하여 리스트 $b$를 만들 수 없다. 따라서 답은 $0$이다.

첫 번째 줄에는 모듈의 수 $n$ ($2 \leq n \leq 10^6$)이 주어진다. 두 번째 줄에는 $n$개의 정수 $a\_1, \ldots a\_n$ ($0 \leq a\_i \leq 10^9$)이 주어진다. 세 번째이자 마지막 줄에는 $n$개의 정수 $b\_1, \ldots, b\_n$ ($0 \leq b\_i \leq 10^9$)이 주어진다.

리스트 $b$는 리스트 $a$를 재배열한 것임이 보장된다.

안전한 분리의 수를 $10^9+7$로 나눈 나머지를 한 정수로 출력한다.