← 返回题目列表

Codeforces · 2144/C

C. 非降序数组

中文机器翻译题面 查看原题

给定两个整数数组 $$$a$$$ 和 $$$b$$$,长度均为 $$$n$$$。

您可以选择索引的任何子集并交换这些位置处的元素(即,为子集中的每个 $$$i$$$ 进行交换($$$a_i$$$, $$$b_i$$$))。考虑索引的子集 好 如果交换后两个数组都按非降序排序。

您的任务是计算良好子集的数量。由于答案可能很大,因此打印它对 $$$998244353$$$ 取模。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 1000$$$)。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 1000$$$)。

对输入的附加约束:至少有一个好的子集。

输出

对于每个测试用例,打印一个整数 - 良好子集的数量,以 $$$998244353$$$ 为模。

示例

输入
复制

3
3
2 1 4
1 3 2
1
4
4
5
2 3 3 4 4
1 1 3 5 6

输出
复制

2
2
8

注意

在第一个示例中,有 $$$2$$$ 好的子集: {1, 3} 和 {2}.

在第二个示例中,有 $$$2$$$ 好的子集: {1} 和 {}.

在第三个示例中,有 $$$8$$$ 好的子集: {1, 2, 3, 4, 5}, {1, 2, 3}, {1, 2, 4, 5}, {1, 2}, {3, 4, 5}, {3}, {4, 5} 和 {}.