Problem H. Odd Shops

时间限制 1000 ms   内存限制 32 MB

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

提交

请先 登录

© 2025 FAQs Contact About