注意

本問はスコア問題ですが，最高得点が存在し，想定解にて最高得点を得ることが出来ます.
ただし，この問題の実行時間制限が厳しいので，最高得点を目指す場合高速な言語の利用を強く推奨します．
writer 解, tester 解の言語はともに C++ で，実行時間はそれぞれ 4024 ms, 673 ms です．

問題文

最初に非負整数 $K$ が与えられ，以下の様に数列 $(A_1, A_2, A_3, \dots )$ を定めます．

• $A_n$ : 最長減少部分列の長さが $3$ であるような全ての要素数 $n$ の順列に対し，最長増加部分列の長さを $K$ 乗した値の総和を $998244353$ で割ったあまり

$30000$ 以下の正整数 $N$ を一つ決め， $N$ 以下の正整数 $n$ に対し $A_n$ をそれぞれ求めてください．

採点方法

一ケースあたりの貴方の得点は $N$ 点となります．また，テストケースは全部で $20$ 個あり，全テストケースの得点の合計が提出の得点となります．
ただし，出力が不正である場合は WA と判定され，AC 以外の判定を一つ以上のテストケースで得た解答の得点は $0$ 点となります．不正な出力とは以下を指します．

• 出力形式に従わなかった
• 誤った出力内容を出力した

コンテスト時間中に得た最高得点で最終順位が決定され，コンテスト期間終了後のリジャッジ，システムテスト等は予定しておりません．

制約

• $0 \leq K \leq 10^9$
• 入力は全て整数で与えられる

入力

$K$

出力

$N$
$A_1\ A_2 \dots A_{N}$

サンプル

100

4
0 0 1 954786991