L. Can you Count?
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given positive integers $$$n,m,k$$$. Count the number of pairs of arrays $$$(a,b)$$$ consisting of only positive integers, such that:

  • $$$a$$$ has length $$$n$$$,
  • Each entry of $$$a$$$ is at most $$$m$$$,
  • $$$b$$$ has length $$$k$$$,
  • $$$\displaystyle \sum^n_{i=1} a=\displaystyle \max^k_{j=1} b$$$.
The answer can be large, so output it modulo $$$998244353$$$.

Since the above is too easy, there are $$$q$$$ queries. Each query specifies a $$$k$$$, and you have to answer the above. The values of $$$n$$$ and $$$m$$$ are fixed throughout the test case.

Input

The first line consists of three integers, $$$n,m,q$$$, $$$1\le n,m\le 9\cdot 10^8$$$ and $$$1\le q\le 10^5$$$.

The second line consists of $$$q$$$ integers, $$$k_1,k_2,\dots,k_q$$$, $$$1\le k_i\le 2\cdot 10^5$$$ denoting the value of $$$k$$$ in each query.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1−5$$$ satisfy $$$q=1, k_i\le 2\cdot 10^4$$$.

Tests $$$6-10$$$ satisfy $$$q=1$$$.

Tests $$$11-15$$$ satisfy $$$k_i\le 2\cdot 10^4$$$.

Tests $$$16-20$$$ satisfy no additional constraints.

Output

Output $$$q$$$ integers, the answer to each query, separated by spaces.

Examples
Input
2 2 4
1 2 3 4
Output
4 20 82 320
Input
30624700 30624770 5
34202 139424 31 40 624
Output
962908989 896508782 487985302 35718864 495214615
Note

—

Problem Idea: culver0412

Problem Preparation: culver0412

Occurrences: Advanced L