题目描述

A 和 B 受到田忌赛马的启发，想进行一次赛马比赛。

一共有 \(n\) （\(1 \le n \le 3 \times 10^5\)）个等级的马，第 \(i\) 个等级中，A 有 \(a_i\) 匹，B 有 \(b_i\) 匹。保证两人的马总数相同，即：

\[ \sum_{i = 1}^{n} a_i = \sum_{i = 1}^{n} b_i \]

每匹马只能参赛一次。比赛规则如下：

• 高等级马对低等级马，必胜。
• 同等级马对同等级马，双方各有 \(50\%\) 概率获胜。

A 和 B 都不知道对方剩余马匹构成，因此都采用完全随机策略：

• 每一轮从自己剩余马中等概率随机选出一匹出战；
• 直到全部马匹比完。

请你计算 A 最终期望赢下的场数，并对 \(998244353\) 取模输出。

输入格式

第一行一个整数 \(T\)，表示测试数据组数。题目要求多组数据，固定为 \(T = 5\)。

对于每组数据：

• 第一行一个整数 \(n\)，表示马的等级数。
• 第二行 \(n\) 个整数 \(a_1, a_2, \dots, a_n\)，满足 \(0 \le a_i \le 10^6\)。
• 第三行 \(n\) 个整数 \(b_1, b_2, \dots, b_n\)，满足 \(0 \le b_i \le 10^6\)。

保证每组数据都满足 \(\sum a_i = \sum b_i\)。

输出格式

对于每组测试数据，设 A 期望赢下的场数为一个最简分数 \(\frac{p}{q}\) （其中 \(q > 0\)，且 \(\gcd(p, q) = 1\)），输出一个整数表示：

\[ p \cdot q^{-1} \bmod 998244353 \]

其中 \(q^{-1}\) 表示 \(q\) 在模 \(998244353\) 意义下的乘法逆元。

可以保证在本题数据范围下，所需逆元一定存在。

样例输入

5
1
1
1
2
1 1
1 1
3
1 0 2
0 2 1
3
2 1 0
0 1 2
4
1 2 1 0
0 1 1 2

样例输出

499122177
1
665496237
166374059
374341633