#P13478. [ABC313Ex] Group Photo
[ABC313Ex] Group Photo
AT_abc313_h [ABC313Ex] Group Photo
题目描述
存在 个人需排队照相, 分为两排。
第一排的人高度分别为:。
第二排的人高度分别为:。
所有人的身高两两不同。只能在各自所在的那一排内调整顺序。用 表示调整后两排从左至右的身高。合法安排满足下列条件。
- $b_{i} > \min(a_i, a_{i - 1}) \text{ }( 2 \le i \le n)$
求有多少种第一排的排列,能为其找到至少一种合法的第二排排列。对同一个第一排排列,无论有多少种合法的第二排排列,都只计一次。
输入格式
共三行。
第一行一个整数表示
第二行 个整数, 分别表示
第三行 个整数, 分别表示
输出格式
输出一个整数,表示答案对 取模的结果。
输入输出样例 #1
输入 #1
3
1 12 6
4 3 10 9
输出 #1
2
输入输出样例 #2
输入 #2
1
5
1 10
输出 #2
0
输入输出样例 #3
输入 #3
10
189330739 910286918 802329211 923078537 492686568 404539679 822804784 303238506 650287940 1
125660016 430302156 982631932 773361868 161735902 731963982 317063340 880895728 1000000000 707723857 450968417
输出 #3
3542400
数据范围
,所有身高都是 到 的整数,且两两不同。