艾姆易艾克斯

【题目描述】

设 $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)$ 尽可能小，请求出这个最小值，以及满足这个最小值的方案数对 $10^9 + 7$ 取模的结果。

【输入格式】

第一行一个正整数 $n$。

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

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

【输出格式】

输出两个整数，分别表示最小的 $Mex(A)$ 和方案数对 $10^9 + 7$ 取模的结果。

【样例输入1】

2
0 1
1 1

【样例输出1】

0 2

【样例说明1】

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

【样例输入2】

4
0 1 2 3
0 1 2 3

【样例输出2】

4 16

【数据规模与约定】

大样例

对于 $100\%$ 的数据 $1 \le n\le 10^5, 0\le A_i,B_i \le 10^9$。

·$Subtask1(30pts): n\le 15$。

·$Subtask2(20pts): n\le 2000, A_i=B_i$。

·$Subtask3(30pts): n\le 2000$。

·$Subtask4(20pts): 无特殊限制$。

【来源】

在此键入。