配点 : $500$ 点

問題文

すぬけ君は、正方形のタイルと正三角形のタイルを無限枚持っています。タイルの辺の長さは全て $1$ です。 これらを使って、辺の長さが $d$ の正 $12$ 角形を作る方法は何通りあるでしょうか。 この答えを $998,244,353$ で割った余りを計算してください。

厳密に述べると、

• タイルを使う枚数に制限はありません。
• 使ったタイルのうち、どの $2$ 枚も重なっていてはいけません。
• 使ったタイルが覆う領域の和集合は、穴のない正 $12$ 角形でなければなりません。
• 二つの作り方について、一方に回転と平行移動を施す (鏡映は不可) ことでもう一方を得られる、すなわち一方における各タイルがもう一方における同種のタイルと完全に一致するとき、これらの作り方を同一とみなします。

制約

• $1 \leq d \leq 10^6$
• 入力中の全ての値は整数である。

入力

入力は標準入力から以下の形式で与えられる。

$d$

出力

答えを出力せよ。

1

1

唯一の作り方を以下の図に示します。