CF2144C Non-Descending Arrays

You are given two integer arrays $ a $ and $ b $ both of length $ n $ . You can choose any subset of indices and swap the elements at those positions (i. e. make a swap( $ a_i $ , $ b_i $ ) for each $ i $ in the subset). A subset of indices is considered good if, after the swapping, both arrays are sorted in non-descending order. Your task is to calculate the number of good subsets. Since the answer can be large, print it modulo $ 998244353 $ .

The first line contains a single integer $ t $ ( $ 1 \le t \le 500 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 100 $ ). The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 1000 $ ). The third line contains $ n $ integers $ b_1, b_2, \dots, b_n $ ( $ 1 \le b_i \le 1000 $ ). Additional constraint on the input: there is at least one good subset.

For each test case, print a single integer — the number of good subsets, taken modulo $ 998244353 $ .

In the first example, there are $ 2 $ good subsets: {1, 3} and {2}. In the second example, there are $ 2 $ good subsets: {1} and {}. In the third example, there are $ 8 $ good subsets: {1, 2, 3, 4, 5}, {1, 2, 3}, {1, 2, 4, 5}, {1, 2}, {3, 4, 5}, {3}, {4, 5} and {}.