問題


五芒星の形をした無色透明のアクリル板と 色のインクがあります。五芒星の中心にある五角形とその周りにある 5 つの三角形をそれぞれ「区画」と呼ぶことにします(五芒星には 6 つの区画があります)。このアクリル板を以下の条件を全て満たすように塗り分けます。

  • 1 つの区画は 1 色のインクで塗りつぶす。
  • 全ての区画を塗る(無色のままの区画を作ることはしない)。
  • 使わない色が有っても良い(例えば、インクが 5 色あっても全体を 3 色で塗り分けて良い)。
  • 五角形の区画を塗った色と同じ色を使って三角形の区画を塗らない。

回転や左右反転を行うことで一致する塗り方は同一の塗り方と考えると、何通りの塗り方が考えられますか?(回転と左右反転を両方とも行うことで初めて一致する複数の塗り方も同一の塗り方と考えます。)

塗り方の数は 64 bit 整数で表現できない値になる可能性があるため、塗り方の数を で割った余りを代わりに求めてください。

制約


入力


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

n

出力


答えを で割った余り( 以上 以下の整数となります)を標準出力に出力してください。

サンプル


入力例1
2
出力例1
2

塗り方 1 塗り方 2

2 色(ここでは青色と桃色にしました)のインクが使えるとき、画像のような 2 通りの塗り方が可能です。

入力例2
1000000000
出力例2
24752

提出


Go (1.14)