配点: $400$ 点

問題文

高橋君の飼い犬の BISCO は, ディスコ株式会社で働いている. ある日, BISCO は 10 年間の功績を認められ, 社長の WISCO からプレゼントとして正方形のチップを $100$ 枚渡された.

BISCO は, これらのチップを以下のように $10$ 行 $10$ 列に並べた.

ここで, 上から $a$ 番目, 左から $b$ 番目にあるチップを「チップ $(a, b)$」と表す.

さて, BISCO はこれらのチップに以下のようにして整数を書き込むことにした.

• まず, 数列 $P = (P_1, P_2, P_3, ..., P_{10})$ と $Q = (Q_1, Q_2, Q_3, ..., Q_{10})$ を決める. これらの項の値はすべて正の整数でなければならない.
• 次に, 各チップ $(i, j)$ に整数 $P_i \\times Q_j$ を書き込む.
• このとき, チップに書き込む整数はすべて $1$ 以上 $N$ 以下でなければならない. この条件が満たされたときのみ, 書き込みが成功する.

BISCO は, 書き込みが成功するような数列 $P, Q$ の決め方が何通り存在するかに興味を持った.
彼のために, 書き込みが成功するような $(P_1, P_2, P_3, ..., P_{10}, Q_1, Q_2, Q_3, ..., Q_{10})$ の組合せとして考えられるものの個数を $1 \\ 000 \\ 000 \\ 007$ で割った余りを求めなさい.

制約

• $N$ は $1$ 以上 $100 \\ 000$ 以下の整数

---

入力

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

$N$

出力

書き込みが成功するような $(P_1, P_2, P_3, ..., P_{10}, Q_1, Q_2, Q_3, ..., Q_{10})$ の組合せの個数を $1 \\ 000 \\ 000 \\ 007$ で割った余りを出力しなさい.

---

入力例 1

1

出力例 1

1

$N = 1$ のとき, 数列 $P, Q$ のすべての項の値を $1$ とするしかない. この場合, すべてのチップに $1 \\times 1 = 1$ が書き込まれ, 書き込みは成功する.

---

入力例 2

2

出力例 2

2047

---

入力例 3

3

出力例 3

118097

---

入力例 4

116

出力例 4

795526989

求めたい組合せの個数を $1 \\ 000 \\ 000 \\ 007$ で割った余りを出力せよ.