Odd Shops

In OddLand, there are many odd shops.
These shops only sell goods weighted from 1 to 10. For every weight i in [1,10], there are $a_i$ kinds of goods weighted i.
The shops are odd because one is only allowed to buy one item or nothing in each shop. And though goods in every shop are different, the array $a$ for each shop is the same.
As you love odd things so much, you wonder for how many total weights, there are odd ways to buy items in n odd shops to achieve this total weight. Since there might be many, output the number mod 998244353.

There are multiple test cases, please read till the end of input file.
For each test case, the first line contain a single integer n, the number of odd shops.
The second line contain ten integers separated by spaces, $a_1,a_2...a_{10}$.
$1 \leq n \leq 10^9, 0 \leq a_i \leq 100$. No more than 10 test cases.

For every test case, output the number of valid total weights mod 998244353.

1
1 2 3 4 5 6 7 8 9 10
2
1 0 0 0 0 0 0 0 0 0
100
1 1 1 1 0 0 0 0 0 0

6
2
35

2018 Multi-University Training Contest 2