問題

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

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

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

塗り方の数は 64 bit 整数で表現できない値になる可能性があるため、塗り方の数を $1000000007 \ (= 10^9 + 7)$ で割った余りを代わりに求めてください。

制約

• $2 \leq n \leq 10^9$
• $n \in \mathbf{Z}$

入力

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

出力

答えを $1000000007 \ (= 10^9 + 7)$ で割った余り($0$ 以上 $1000000006$ 以下の整数となります)を標準出力に出力してください。

サンプル

2

2

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

1000000000

24752