题目描述

Unputdownable 手中有一个长度为 $n$ 的排列 $a$。

他在练习单调栈的时候用程序对于每一个 $i$ 求出了最大的 $l_i$ 使得 $a_{l_i} < a_i$ 且 $l_i<i$，以及最小的 $r_i$ 使得 $a_{r_i}<a_i$ 且 $r_i>i$。

特别的，若这样的 $l_i$ 不存在，则定义为 $0$，不存在的 $r_i$ 则定义为 $n+1$。

某日 Unputdownable 忘记了排列 $a$，而且只剩余分别重排后的 $l$ 和 $r$ 数组了，你能帮助他还原原来的排列 $a$ 吗？

随后由于他发现无法还原 $a$，你只要告诉他有多少种可能的原排列 $a$。

答案对于 $998244353$ 取模，数据保证至少存在一种方案。

输入格式

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数，表示重排后的 $l$。

第三行输入 $n$ 个整数，表示重排后的 $r$。

输出格式

输出一行，包含一个整数，表示可能的排列数量对 $998244353$ 取模后的值。

5
3 1 0 0 4
6 3 6 3 6

6

提示

样例解释 1

一种可能的排列是 $\{2,5,1,3,4\}$，$l$ 数组是 $\{0,1,0,3,4\}$，$r$ 数组是 $\{3,3,6,6,6\}$。

本题采用捆绑测试。

• Subtask 1（5 pts）：$n\leq 8$。
• Subtask 2（15 pts）：$r_i\geq n$。
• Subtask 3（15 pts）：$n\leq 2000$，保证存在一个排列 $a$ 满足排列 $a$ 所求出的 $l,r$ 即为给定的。
• Subtask 4（25 pts）：$n\leq 10^6$，保证存在一个排列 $a$ 满足排列 $a$ 所求出的 $l,r$ 即为给定的。
• Subtask 5（40 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \leq n \leq 10^6$，$0 \leq l_i,r_i \leq n+1$，数据保证至少存在一种方案。