28408번 - 나무늘보

문제

$N$개의 정점으로 구성된 이진트리에 거주하고 있는 나무늘보가 있다. 각 정점에는 1ドル$부터 $N$까지 번호가 적혀 있다.

나무늘보는 현재 거주지를 신고하기 위해 거주하고 있는 이진트리의 전위, 후위 순회 결과를 적어 두었다. 이진트리의 전위, 후위 순회의 정의는 아래와 같다.

• 전위 순회: 현재 정점을 방문한 후 왼쪽, 오른쪽 순서로 서브 트리를 전위 순회한다.
• 후위 순회: 왼쪽, 오른쪽 순서로 서브 트리를 후위 순회한 후 현재 정점을 방문한다.

나무늘보는 적어 둔 전위, 후위 순회 결과로 이루어진 이진트리가 여러 개 존재할 수도 있고, 결과를 잘못 적어서 이진트리가 존재하지 않을 수도 있다는 사실을 알게 되었다.

당신은 나무늘보가 적어 둔 전위, 후위 순회 결과가 주어졌을 때 동일한 순회 결과를 가지는 이진트리의 개수를 알아내야 한다.

입력

첫 번째 줄에 이진트리의 정점 개수 $N (1 \le N \le 500,000円)$이 주어진다.

두 번째 줄에는 전위 순회 결과를 나타내는 정수 $N$개가 공백으로 구분되어 주어진다.

세 번째 줄에는 후위 순회 결과를 나타내는 정수 $N$개가 공백으로 구분되어 주어진다.

입력으로 들어오는 전위, 후위 순회 결과는 1ドル$부터 $N$까지의 정수가 중복 없이 배치된 순열이다.

출력

문제의 답을 998ドル,円 244,円 353$으로 나눈 나머지를 한 줄에 출력한다.

제한

힌트