Little $W$ is having a voice conversation with a girl, but she does not want to talk to him. Therefore, for each turn, the girl independently chooses a real number $l$ uniformly at random from $[0, 10]$ and sends him a voice message of length $l$ seconds. However, little $W$ on the other side of the screen is unaware of this. When the length of the girl's voice message becomes shorter, little $W$ feels anxious, thinking he has not found a topic the girl likes. When a voice message is longer than the previous one, little $W$ feels overjoyed, as he believes he has found a topic.

More specifically, assume little $W$ and the girl have $n$ rounds of conversation. We can represent the lengths of the $n$ voice messages sent by the girl as a sequence $a_1, a_2, \dots, a_n$, where $a_i$ is the length of the $i$-th voice message, which is chosen uniformly at random from $[0, 10]$ and is independent of the other elements. If some $i$ ($1 \leq i < n$) satisfies $a_i < a_{i+1}$, then little $W$ will feel overjoyed once. The total number of times little $W$ feels overjoyed during these $n$ rounds of conversation is the number of indices $i$ such that $a_i < a_{i+1}$ ($1 \leq i < n$).

Let $F_k$ be the probability that little $W$ feels overjoyed $k$ times when there are $n$ voice messages.

Calculate $F_0, F_1, \dots, F_{n-1}$.

The answer should be taken modulo $998244353$.

Input

A single positive integer $n$.

Output

$n$ integers, representing $F_0, F_1, \dots, F_{n-1}$.

Examples

Input 1

3

Output 1

166374059 665496236 166374059

Input 2

10

Output 2

370705776 185074360 753392795 76402225 111791374 111791374 76402225 753392795 185074360 370705776

Subtasks

Subtask 1 (10 pts): $1 \leq n \leq 10$

Subtask 2 (10 pts): $1 \leq n \leq 20$

Subtask 3 (30 pts): $1 \leq n \leq 400$

Subtask 4 (10 pts): $1 \leq n \leq 2000$

Subtask 5 (40 pts): $1 \leq n \leq 100000$