Harsh Comments

Time limit1sMemory limit1024 MB

Summary

Comments are deleted one at a time with probability proportional to downvotes; find the expected number of deletions until all of the first N comments are gone.

Level: Medium7 of 10
Topics: Probability, Combinatorics, Math, Dynamic programming
Solved: No attempts yet

Problem

A blog has $N+M$ harsh comments. You wrote $N$ of them, and the $i$ -th of your comments has $A_i$ downvotes. The $i$ -th of the other $M$ comments has $B_i$ downvotes.

Mike will delete the comments one by one by repeating the following operation:

Choose a comment at random and delete it. More precisely, let $x_1,x_2,\ldots,x_k$ be the downvote counts of the remaining comments. He chooses the $i$ -th of them with probability $x_i/\left(\sum_{1\leq j \leq k}x_j \right)$ and deletes it.

The choices in the operations are independent.

Find the expected number of operations Mike performs until he has deleted all of your comments. The answer is a rational number, so print it modulo $998244353$ as usual. It can be proved that this representation is always possible under the constraints of this problem.

Input

The first line contains the integers $N$ and $M$ ( $1 \leq N,M \leq 100$ ).

The second line contains the integers $A_1,A_2,\ldots,A_N$ ( $1 \leq A_i \leq 100$ ).

The third line contains the integers $B_1,B_2,\ldots,B_M$ ( $1 \leq B_i$ , $\sum_{1 \leq i \leq N} A_i + \sum_{1 \leq i \leq M} B_i < 998244353$ ).

Output

Print the answer.

Examples3

Example 1
Input
```
1 2
1
1 1
```
Expected output
```
2
```
Example 2
Input
```
1 1
2
1
```
Expected output
```
332748119
```
Example 3
Input
```
3 3
2 3 5
7 11 900000000
```
Expected output
```
636512475
```