Big-headed Stickman teaches Kaka how to play Goose Goose Duck. Big-headed says: "This game consists of 13 players, so you must first learn to count. This is number one, this is number two, ...". In short, Kaka spent ten minutes fully understanding the game, and of course, learned how to count.

After learning to count, Kaka felt he was very good at it, so he came up with a counting problem. You, being clever, must also be good at counting, right? Please solve this little problem before going to play Goose Goose Duck.

For a non-negative integer $s$, a "Kaka partition" is defined as representing $s$ as a sum of several positive integers, where the order does not matter, and it satisfies an additional constraint: for every integer $i$, the number of times it appears in the partition must be either 0 or an odd number ($1, 3, 5, \dots$).

For example, there are only two valid Kaka partitions for 4: 4 and 3+1. In 2+2, 2 appears 2 times; in 2+1+1, 1 appears 2 times; both are invalid. Note that 3+1 and 1+3 are considered the same partition.

For a non-negative integer $n$, let $p(n)$ be the number of Kaka partitions of $n$, and define $p(0) = 1$.

Given $N$, you need to output $p(0), p(1), \dots, p(N)$ modulo 998244353.

Input

A single line containing an integer $N$ ($0 \le N \le 1000000$).

Output

Output a single line containing $N+1$ integers, which are $p(0), p(1), \dots, p(N)$ modulo 998244353, respectively.

Examples

Input 1

10

Output 1

1 1 1 3 2 5 6 9 9 16 20

Note

When 4 is partitioned, only 4 and 3+1 are valid, so $p(4) = 2$. Partitions like 2+2 and 2+1+1 are invalid because some number appears an even number of times.