Problem Description

Given two sequences $A, B$ of length $n$, satisfying:

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

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

Let $\pi$ be a permutation of length $n$. Define the value function $f(\pi)$:

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

All permutations are equally likely. Find the expected value of $f(\pi)$ modulo $998244353$.

That is, compute:

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

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers, denoting $A_i$.

The third line contains $n$ integers, denoting $B_i$.

Output Format

Output one line containing one integer, the answer.

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

114102208

Hint

This problem uses bundled testdata.

Subtask ID	Score	Special Constraints
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	None

For $100\%$ of the data, $1\le n\le 5000$, $1\le A_i,B_i\le 10^9$.

Translated by ChatGPT 5