Description

给定一个整数 $k$ ，输出第 $k$ 行的二项式系数。

规定，第一行为 $1$， 第二行为 $1 \ 1$ ，第三行为 $1 \ 2 \ 1$，依此类推。

由于某些系数会很大，请都模 $998 \ 244 \ 353$ 输出。

Format

Input

一个整数 $k$。

$1 \le k \le 10^6$ 。

Output

输出一行，输出第 $k$ 行的二项式系数，以空格隔开。

Samples

4

1 3 3 1