题目描述

给定两个长度为 $n$ 的序列 $A,B$，满足：

• $\forall 1\le i<n,A_i \ge A_{i+1}$

• $A_n\ge \min\limits_{i=1}^n(B_i)$

$\pi$ 是一个长度为 $n$ 的排列，定义价值函数 $f(\pi)$：

$$f(\pi)=\prod_{i=1}^n\min(A_i,B_{\pi(i)})$$

每种排列出现的概率相等，求 $f(\pi)$ 的期望对 $998244353$ 取模的结果。

即求:

$$\left(\dfrac{1}{n!}\sum_\pi f(\pi)\right) \bmod 998244353 $$

输入格式

第一行输入一个整数 $n$。

第二行 $n$ 个整数表示 $A_i$。

第三行 $n$ 个整数表示 $B_i$。

输出格式

输出一行一个整数，为答案。

8
15 14 13 10 9 6 3 2 
2 10 8 2 9 1 10 2 

114102208

提示

本题采用捆绑测试。

子任务编号	分值	特殊限制
1	5	$1\le n\le 8$
2	35	$1\le n\le 50$
3	20	$A_n\ge \max\limits_{i=1}^n(B_i)$
4	40	无

对于 $100\%$ 的数据满足 $1\le n\le 5000$，$1\le A_i,B_i\le 10^9$。