A - Dodecagon 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500 点

問題文

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

厳密に述べると、

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

制約

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

入力

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

d

出力

答えを出力せよ。

入力例 1

1

出力例 1

1

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

Score : 500 points

Problem Statement

Snuke has infinite number of square tiles and regular triangular tiles with side lengths 1. How many ways are there to form a regular dodecagon (12-sided polygon) with side lengths d using the tiles? Compute the answer modulo 998,244,353.

Formally speaking,

  • He can use an arbitrary number of tiles.
  • No two tiles may overlap.
  • The union of the regions filled by the tiles must be a regular dodecagon without holes.
  • We consider two ways to be the same if we can change one way to the other way by rotations and translations (but not reflections), such that each tile perfectly matches with a tile of the same type.

Constraints

  • 1 \leq d \leq 10^6
  • All values in the input are integers.

Input

Input is given from Standard Input in the following format:

d

Output

Print the answer.

Sample Input 1

1

Sample Output 1

1

The following picture shows the only way.