集体照

题目描述

$(2N+1)$ 个人排成前后两列拍摄集体照。 前列有 $N$ 人,其中第 $i$ 人的身高为 $A_i$。 后列有 $N+1$ 人,其中第 $i$ 人的身高为 $B_i$。 保证这 $2N+1$ 人的身高互不相同。 在前列、后列各自内部,可以自由调整人的排列顺序。

假设前列从左到右的身高为 $a_1,a_2,\dots,a_N$,后列从左到右的身高为 $b_1,b_2,\dots,b_{N+1}$。 当满足以下所有条件时,称该排列为好的排列:

• 对所有 $i\ (2 \le i \le N)$,有 $a_i \lt b_i$ 或 $a_{i-1} \lt b_i$。
• $a_1 \lt b_1$。
• $a_N \lt b_{N+1}$。

前列的排列方式共有 $N!$ 种,求其中能通过适当调整后列的排列方式使之成为好的排列的排列数,对 $998244353$ 取模。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_{N+1}$

输出格式

将答案作为整数输出。

样例

3
1 12 6
4 3 10 9

2

当 $a = (1,12,6)$ 时,可以令 $b = (4,3,10,9)$ 等来使排列成为好的排列。 当 $a = (6,12,1)$ 时,可以令 $b = (10,9,4,3)$ 等来使排列成为好的排列。 当 $a$ 为其余 4 种排列时,无论后列如何排列(即 $24$ 种 $b$ 中的任意一种),都无法使排列成为好的排列。

因此答案为 2。

1
5
1 10

0

10
189330739 910286918 802329211 923078537 492686568 404539679 822804784 303238506 650287940 1
125660016 430302156 982631932 773361868 161735902 731963982 317063340 880895728 1000000000 707723857 450968417

3542400

数据范围

• $1 \le N \le 5000$
• $1 \le A_i,B_i \le 10^9$
• $A_i \neq A_j\ (1 \le i \lt j \le N)$
• $B_i \neq B_j\ (1 \le i \lt j \le N+1)$
• $A_i \neq B_j\ (1 \le i \le N, 1 \le j \le N+1)$
• 输入均为整数