#P17852. [Ontak2019]MAL

[Ontak2019]MAL

— 两笔作画

有一块 n×nn\times n 的白色画布,划分成单位方格。行从上到下、列从左到右编号。

画家只画两笔。第一笔从 (1,1)(1,1) 出发到 (n,n)(n,n),每次向右或向下移动一格。第二笔从 (n,n)(n,n) 回到 (1,1)(1,1),每次向左或向上移动一格。两笔经过的所有格子都会变黑,经过两次仍只算一个黑格,起点和终点也会被涂黑。

给定每一列应有的黑格数 cic_i 以及每一行应有的黑格数 rir_i,判断能否按要求完成画作,并计算画法数量,对 109+710^9+7 取模。

两种画法不同,当且仅当存在一个格子,在某一笔中被一种画法经过、而另一种画法的同一笔没有经过。因此两笔有区别,只有最终黑格集合相同并不一定是同一种画法。

输入格式

第一行一个整数 nn。

第二行 nn 个整数 c1,…,cnc_1,\ldots,c_n,表示各列黑格数。

第三行 nn 个整数 r1,…,rnr_1,\ldots,r_n,表示各行黑格数。

输出格式

第一行:可行时输出 YES,否则输出 NO。

第二行输出画法数量对 109+710^9+7 取模的结果,不可行时输出 0。

原站对仅正确判断可行性的程序给予该测试30%的分数,但仍要求输出第二行。本题标程输出完整答案。

数据范围

2≤n≤1062\le n\le10^6,0≤ci,ri≤n0\le c_i,r_i\le n。

子任务 nn 上限 分值
1 20 10
2 100
3 1000 20
4 10000
5 100000
6 1000000

英文叙述中有一处将 r,cr,c 对调;这里与原题输入格式及波兰文一致:先列数 cc,后行数 rr。

样例 1

输入:

3
2 2 1
1 2 2

输出:

YES
1

样例 2

输入:

3
3 3 3
1 1 2

输出:

NO
0