8527: Easy Counting Problem

We consider a string to be good if it satisfies the following conditions:

•  It consists of decimal digits less than $w$.
•  Digit $i$ appears at least cic_ici times.

We consider two strings to be different if they are different in length or there exists an integer $i$ such that the letters in their $i$-th position are different.
The problem in the textbook asks for the number of different good strings of length $n$.

The first line contains a single integer $w$ (2≤w≤102 \leq w \leq 102≤w≤10), indicating that a good string consists of decimal digits less than $w$.
The second line contains $w$ integers c0,c1,…,cw−1c_0,c_1,\ldots,c_{w-1}c0,c1,…,cw−1 (1≤ci≤500001 \leq c_i \leq 500001≤ci≤50000, c0+c1+…+cw−1≤50000c_0+c_1+\ldots+c_{w-1} \leq 50000c0+c1+…+cw−1≤50000), indicating that the decimal digit $i$ appears at least cic_ici times in a good string.
The third line contains a single integer $q$ (1≤q≤3001 \leq q \leq 3001≤q≤300), indicating the number of queries.
Each of the next $q$ lines contains a single integer $n$ (1≤n≤1071 \leq n \leq 10^71≤n≤107), indicating the length of the string.

For each query, output an integer in a single line indicating the number of different good strings of length $n$. As the answer may be large, please output the answer modulo 998244353.

2
1 1
3
3
5
7

6
30
126

If we set $n=3$, w=2w=2w=2, c0=c1=1c_0=c_1=1c0=c1=1, then the answer is $6$, including $\text{001},\text{010},\text{011},\text{100},\text{101},\text{110}$.