题目描述

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

给定长度为 $n$ 的两个序列 $A$ 和 $B$，对于每个位置 $i(1\le i\le n)$ 你可以选择交换 $A_i$ 和 $B_i$ 或者不交换，现在你希望最终的 $\operatorname{mex}(A)$，请求出这个最小值，以及满足这个最小值的方案树对 $10^9+7$ 取模的结果。

输入格式

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

第二行 $n$ 个非负整数，$A_1,\ldots,A_n$。

第三行 $n$ 个非负整数，$B_1,\ldots,B_n$。

输出格式

输出两个整数，分别表示最小的 $\operatorname{mex}$ 值和方案数对 $10^9+7$ 取模的结果。

样例

2
0 1
1 1

0 2

容易发现必须交换 $A_1$ 和 $B_1$，$A_2,B_2$ 可以选择交换或者不交换，最终的 $\operatorname{mex}$ 为 $0$。

4
0 1 2 3
0 1 2 3

4 16

在附加文件中有两组大样例。

数据范围

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