Problem Description
Accidentally, Cupid, god of desire has hurt himself with his own dart and fallen in love with Psyche.
This has drawn the fury of his mother, Venus. The goddess then throws before Psyche a great mass of mixed crops.
There are
n heaps of crops in total, numbered from
1 to
n.
Psyche needs to arrange them in a certain order, assume crops on the
i-th position is
Ai.
She is given some information about the final order of the crops:
1. the minimum value of
A1,A2,...,Ai is
Bi.
2. the maximum value of
A1,A2,...,Ai is
Ci.
She wants to know the number of valid permutations. As this number can be large, output it modulo
998244353.
Note that if there is no valid permutation, the answer is
0.
Input
T
(1≤T≤15), which denotes the number of testcases.
For each test case, the first line of input contains single integer
n
(1≤n≤105).
The second line contains
n integers, the
i-th integer denotes
Bi
(1≤Bi≤n).
The third line contains
n integers, the
i-th integer denotes
Ci
(1≤Ci≤n).
Output
998244353.
Sample Input
2
3
2 1 1
2 2 3
5
5 4 3 2 1
1 2 3 4 5
Sample Output
Hint
#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
using namespace std;
typedef __int64 LL;
const int low(int x) { return x&-x; }
const int N = 1e5 + 10;
const int mod = 998244353;
const int INF = 0x7FFFFFFF;
int T, n, a[N], b[N];
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
int ans = 1, t = 1;
rep(i, 1, n) scanf("%d", &a[i]);
rep(i, 1, n) scanf("%d", &b[i]);
rep(i, 2, n)
{
if (a[i] > a[i - 1]) ans = 0;
if (b[i] < b[i - 1]) ans = 0;
if (a[i] != a[i - 1] && b[i] != b[i - 1]) ans = 0;
}
if (a[1] != b[1]) ans = 0;
rep(i, 2, n)
{
--t;
if (a[i] != a[i - 1]) { t += a[i - 1] - a[i]; continue; }
if (b[i] != b[i - 1]) { t += b[i] - b[i - 1]; continue; }
ans = (int)(1LL * ans * t % mod);
}
printf("%d\n", ans);
}
}