A. Atcoder Problem
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Print the number, modulo $$$998244353$$$, of integer sequences $$$A = (A_1, A_2, \dots, A_N)$$$ with length $$$N$$$ that satisfy both of the following conditions.

  • $$$0\leq A_1 \leq A_2\le \cdots \leq A_N \leq M$$$
  • $$$A_1 \oplus A_2\oplus \cdots \oplus A_N = X$$$

The problem is too easy, so output the answer for each $$$N = 1, 2, \dots, NMAX$$$.

Input

In the first line, $$$NMAX, M, X$$$ ($$$1\leq NMAX \leq 10^5, 0\leq M, X \lt 2^{60}$$$).

Output

$$$NMAX$$$ lines — the answers for $$$N = 1, 2, \dots, NMAX$$$.

Examples
Input
5 6 7
Output
0
3
7
25
49
Input
10 100 0
Output
1
101
1418
38280
756912
13403840
203823022
755806367
368916768
79402702