I. Aeroplane Chess
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
In every real man a child is hidden that wants to play.
— Friedrich Nietzsche, Thus Spoke Zarathustra

On a day that could not be more ordinary, KP unexpectedly received an anonymous birthday gift — an aeroplane chess!

The gift evoked memories of his childhood, but after several hours of playing, he had a doubt:

During the Home Zone Backtrack, if the chess is on the $$$i$$$-th cell, what is the expected number of rolls required to reach the end?

Formally, assume that the chess is placed on an axis, where the point $$$\mathtt{0}$$$ denotes the end.

During one operation, you will randomly choose a number $$$y$$$ $$$(1 \leq y \leq n)$$$. Assume that the point of the chess is $$$x$$$:

  • if $$$y \lt x$$$, then $$$x := x - y$$$;
  • if $$$y \gt x$$$, then $$$x:= y - x$$$;
  • Otherwise, the game ends.

Now you need to process $$$q$$$ queries, each query consists of a single integer $$$x$$$, denoting the point of the chess.

For each query, you need to output the expected number of operations needed to reach the end of the game.

It can be shown that the answer can be represented as $$$P / Q$$$, where $$$P$$$, $$$Q$$$ are coprime integers and $$$Q \not \equiv 0 \pmod {998244353}$$$. Print the value of $$$P \times Q^{-1} \pmod {998244353}$$$.

Input

The first line contains two integers $$$n$$$, $$$q$$$ $$$(1 \leq n \leq 500, 1 \leq q \leq 2 \times 10 ^ 5)$$$.

The $$$i$$$-th of the next $$$q$$$ lines contains a single integer $$$x$$$ $$$(1 \leq x \leq 10 ^ 6)$$$, denoting the point of the chess.

Output

For each query, output a single integer, denoting the answer to the query modulo $$$998244353$$$.

Example
Input
2 2
1
114514
Output
2
64376993
Note

In the first test case, the chess is on point $$$\mathtt{1}$$$, and the following will happen:

  1. You randomly choose $$$1$$$ for possibility $$$\frac{1}{2}$$$. After that, $$$1 = x$$$, and you reach the end.
  2. You randomly choose $$$2$$$ for possibility $$$\frac{1}{2}$$$. After that, $$$2 \gt x$$$, so $$$x := 2 - x = 1$$$. Then you randomly choose $$$1$$$ for possibility $$$\frac{1}{2}$$$. After that, $$$1 = x$$$, and you reach the end.
  3. ...

It can be shown that the expected number of operations to reach the end equals:

$$$\displaystyle E = 1 \times \frac{1}{2} + 2 \times \frac{1}{2^2} + 3 \times \frac{1}{2^3} + \ldots = 2.$$$

In the second test case, note that you need to print the answer modulo $$$998244353$$$.