All submissions for this problem are available.You are given $K$ different colors of beads. A bead of the $i$-th color has a weight $w_i$. You have infinitely many beads of each color. All the beads of the same color have the same weight. You have to answer $q$ independent queries. For each query, you will be given $S$. You have to form a necklace consisting of $n$ beads such that the total weight of the necklace is $S$. You can use any number of beads of a single color (possibly zero). Count the number of distinct possible necklaces you can make. Two necklaces will be considered the same if one can be rotated to another. ### Input - First line contains $n$, denoting the size of the necklace. - Second line contains $K$, denoting the number of different colors. - Third line contains $K$ space separated integers, where the $i$-th integer $w_i$ denotes the weight of a bead of color $i$. - Fourth line contains $q$, denoting the number of queries. - Each of the next $q$ lines will contain a single integer $S$, denoting the total weight of the necklace for this query. ### Output For each query, output in a new line, the number of valid necklaces mod $998244353$. ### Constraints - $1 \le n, q, K, w_i, S \le 10^5$ - $n$ will be a power of two ### Example Input ``` 4 4 1 2 3 4 4 5 6 7 8 ``` ### Example Output ``` 1 3 5 9 ``` ### Explanation For S = 6, three ways to form the necklace are: - 1 -> 1 -> 1 -> 3 - 1 -> 1 -> 2 -> 2 - 1 -> 2 -> 1 -> 2 Please note, we do not count 2 -> 1 -> 1 -> 2 because it is just a rotation of 1 -> 1 -> 2 -> 2.
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.