#P9604. 艾姆易艾克斯

艾姆易艾克斯

题目描述

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

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

输入格式

第一行一个正整数 nn。

第二行 nn 个非负整数,A1,…,AnA_1,\ldots,A_n。

第三行 nn 个非负整数,B1,…,BnB_1,\ldots,B_n。

输出格式

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

样例

2
0 1
1 1
0 2

容易发现必须交换 A1A_1 和 B1B_1,A2,B2A_2,B_2 可以选择交换或者不交换,最终的 mex⁡\operatorname{mex} 为 00。

4
0 1 2 3
0 1 2 3
4 16

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

数据范围

对于全部数据,1≤n≤1051\le n\le 10^5,0≤Ai,Bi≤1090\le A_i,B_i\le 10^9。

测试点编号 n≤n\le 特殊限制
1∼31\sim 3 1515
4∼54\sim 5 2×1032\times 10^3 Ai=BiA_i=B_i
6∼86\sim 8
9∼109\sim 10 10510^5