1258 : Rolling For Days

Description

In the game TFT, players need to buy units in the store to build up a powerful lineup against other players. Only one-star units will be refreshed in the store, three identical one-star units can be synthesized into a corresponding two-star unit, and three identical two-star units can be synthesized into a corresponding three-star unit. Higher star units will obviously be much more powerful than lower star units. The units refreshed in the store are random, and refreshing requires coins. So it’s possible that you can’t get the units you want although having a lot of coins.

As a disciplined player, you’re curious about just how many refreshes are needed to complete a particular deck. To that end, you’re going to start by solving the following simplified problem:

There are a total of \(n\) cards in the store’s card pool, which are categorized into \(m\) kinds, where the \(i\)-th kind of card has a total of \(a_i\) cards. You have decided on your target deck, and your target deck requires \(b_i\) cards of the \(i\)-th kind. Each time you refresh, one card will be randomly drawn from the remaining cards in the card pool with equal probability. If the drawn card is not needed (i.e., the number of cards in this kind already purchased is equal to the number that your target deck requires), you’ll put the card right back into the card pool; otherwise, you’ll purchase the card and remove it from the card pool. How many refreshes do you expect to need to complete your target deck? Since the answer may be large and floating point errors cannot be ignored, please output the answer modulo \(998244353\).

Formally, let \(M=998244353\) . It can be shown that the answer can be expressed as an irreducible fraction \(\frac{p}{q}\) , where \(p\) and \(q\) are integers and \(q\not\equiv 0\pmod M\) . Output the integer equal to \(p\cdot q^{-1} \bmod M\) . In other words, output such an integer \(x\) that \(0\le x<M\) and \(x\cdot q\equiv p\pmod M\) .

Input

The first line contains two integers \(n,m(1\le n\le 1000;1\le m\le 12)\) , denoting the total number of cards and the number of kinds.

The second line contains \(m\) integers \(a_1,a_2,...,a_m(1\le a_i\le n,\sum_{i=1}^ma_i=n)\) , denoting the numbers of cards of each type.

The third line contains \(m\) integers \(b_1,b_2,...,b_m(0\le b_i\le a_i)\) , denoting the numbers of cards required for your target deck.

Output

Output a single integer, denoting the expect number of refreshes modulo \(998244353\) .

Sample

2 2
1 1
1 1
##CASE##
4 2
2 2
2 1
##CASE##
1000 12
101 43 34 281 23 24 12 25 66 222 145 24
37 43 27 257 5 11 12 19 62 41 87 13

2
##CASE##
582309210
##CASE##
265294941

Hint

The answer for sample case #1 is \(\frac{49}{12}\).

Source

Author

FUDAN