← 返回题目列表

AtCoder · ddcc2018_qual_c

C. 芯片物语~白银版~

中文机器翻译题面 查看原题

配点: 400 点

問題文

高桥的狗 BISCO 在迪斯科公司工作。有一天,BISCO因其10年的成就而受到表彰,并被武钢总裁赠送了一块方形芯片作为礼物。 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 后的余数。