Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 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 で割った余りを出力せよ.