题目描述

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

厳密に述べると、

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

输入格式

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

$d$

输出格式

答えを出力せよ。

题目大意

Snuke 有无限个边长为 $1$ 的正方形和正三角形瓷砖。有多少种不同的方法可以用这些瓷砖组成一个边长为 $d$ 的正十二边形？请计算方案数并对 $998\ 244\ 353$ 取模。

具体地说：

• Snuke 可以使用任意数量的瓷砖。
• 方案中没有两块瓷砖是重叠的。
• 瓷砖所填充的区域必须是一个无孔的正十二边形。
• 如果我们可以将一种方案通过旋转和平移得到另一种方案，则这两个方案是相同的。

输入共一行，一个正整数 $d$，表示正十二边形的边长。

输出共一行，一个正整数，表示方案数对 $998\ 244\ 353$ 取模后的结果。

对于 $100\ \%$ 的数据，$1 \le d \le 10^{6}$。

1

1

提示

制約

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

Sample Explanation 1

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