题目描述

给定两个整数序列 $A=(A_1, \dots, A_N)$ 和 $B=(B_1, \dots, B_N)$，找到满足以下条件的非空子集 $S$ 的数量：

• 对于所有 $i \in S$，有 $\max_{i \in S} A_i \geq \sum_{i \in S} B_i$。

由于计数可能非常大，将其对 $998244353$ 取模后输出。

约束条件

• $1 \leq N \leq 5000$
• $1 \leq A_i, B_i \leq 5000$
• 输入中的所有值都是整数。

输入格式

从标准输入读入数据，输入格式如下：

$N$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_N$

输出格式

输出满足题目条件的子集 $S$ 的数量，将结果对 $998244353$ 取模。

示例输入1

2
3 1
1 2

示例输出1

2

集合 $\\{1,2,\\ldots,N\\}$ 有三个子集：$\\{1\\}$，$\\{2\\}$ 和 $\\{1,2\\}$。

• 对于 $S=\\{1\\}$，有 $\max_{i \in S} A_i=3$ 且 $\sum_{i \in S} B_i=1$。
• 对于 $S=\\{2\\}$，有 $\max_{i \in S} A_i=1$ 且 $\sum_{i \in S} B_i=2$。
• 对于 $S=\\{1,2\\}$，有 $\max_{i \in S} A_i=3$ 且 $\sum_{i \in S} B_i=3$。

因此，满足条件 $\max_{i \in S} A_i \geq \sum_{i \in S} B_i$ 的子集有两个：$\\{1\\}$ 和 $\\{1,2\\}$。

示例输入2

2
1 1
2 2

示例输出2

0

可能没有满足条件的子集。

示例输入3

20
1937 3980 2689 1208 3640 1979 581 2271 4229 3948 3708 1522 4161 4661 3797 96 3388 3395 2920 2247
4485 2580 174 1156 3770 3396 3558 3500 3494 479 269 3383 1230 1711 3545 3919 134 475 3796 1017

示例输出3

476