题目描述

设$A$ 是非负整数序列，定义 $Mex(A)$ 为序列 A 中没有出现的最小的非负整数。比如 $Mex(0,1, 3, 3, 2) = 4$, $Mex(5, 0, 0, 1, 4) = 2$。

给定长度为 $n$ 的两个序列 $A$ 和 $B$，对于每个位置 $i(1 ≤ i ≤ n)$ 你可以选择交换 $A_i$ 和 $B_i$ 或者不交换，现在你希望最终的 $Mex(A)$ 尽可能小，请求出这个最小值，以及满足这个最小值的方案数对 $1e9 + 7$ 取模的结果。

输入格式

第一行一个正整数 n。

第二行 n 个非负整数 $A_1, ..., A_n$。

第三行 n 个非负整数 $B_1, ..., B_n$。

输出格式

输出两个整数，分别表示最小的 $Mex$ 值和方案数对 $1e9 + 7$ 取模的结果。

样例

2
0 1
1 1

0 2

4
0 1 2 3
0 1 2 3

4 16

样例解释

容易发现必须交换 $A_1$ 和 $B_1$，$A_2$,$B_2$ 可以选择交换或者不交换，最终的 $Mex$ 为 $Mex(1, 1) = 0$。

大数据

限制条件

对于全部数据，$1 ≤ n ≤ 10^5, 0 ≤ A_i, B_i ≤ 10^9$。