TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P8942
  • 题目
  • P8942最小公倍数
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 5s 256MB
    问题描述

    给出一个数 \(n\),你可以将它拆成一个长度任意的序列 \(a_i\) 满足 \(n = \sum_{i=1}^ka_i\),一个集合的 \(lcm\) 定义为集合中所有数的 \(lcm\)(空集的 \(lcm\) 为 $1$),一个序列的权值定义为:这个序列的所有子集中不同 \(lcm\) 的个数,要求最大化你拆出来序列的权值,答案对 $10^9 + 7$ 取模。

    输入格式

    一行一个正整数 \(n\)

    \(n\leq 10^5\)

    输出格式

    一行一个非负整数,表示最大权值对 $10 ^ 9 + 7$取模后的值

    样例输入

    5

    样例输出

    4

    提示

    $5 = 2 + 3$,\(lcm\) 有 $1,2,3,6$ 四种