Migrated from Lutece 2885 easy BBQ problem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

你现在有一个烤架，烤架能够抽象的看成一个 $n\times n$ 的矩阵。

你现在有 $k$ 串烤肉，烤肉的签子是一个满足从起点出发，只能向下或者向右延展的一条路径。

你现在有 $2k$ 个支点，在第 $1$ 列有 $k$ 个， 在第 $n$ 列有 $k$ 个。

你现在想知道，有多少种方案，可以使得烤架上放上 $k$ 个从第一列的某个支点出发，到第 $n$ 列的某个支点结束的签子，并且签子直接不能出现交叉的情况（PS:两两签子间起点，终点不能相同）。

请求解方案数对998244353取模的值

Input

第一行输入两个整数 $n,k$

第二行输入 $k$ 个整数 $a_i$，表示第 $1$ 列的支点位置。

第三行输入 $k$ 个整数 $b_i$，表示第 $n$ 列的支点位置。

保证支点顺序按照从小到大排序，并且坐标均合法。

Output

输出方案数对998244353取模的值

Samples

5 2
1 2
3 4

50

Constraints

$1\le n \le 10^5 , 1\le k \le 100,1\le a_i,b_i\le n$，保证 $a_i<a_{i+1},b_i<b_{i+1}$。

Resources

2022 UESTC ICPC Training for Math and Geometry