#2544. 「JXOI2018」游戏

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

九条可怜是一个富有的女孩子。她长大以后创业了,开了一个公司。 但是管理公司是一个很累人的活,员工们经常背着可怜偷懒,可怜需要时不时对办公室进行检查。

可怜公司有 n 个办公室,办公室编号是 l\sim l+n-1 ,可怜会事先制定一个顺序,按照这个顺序依次检查办公室。一开始的时候,所有办公室的员工都在偷懒,当她检查完编号是 i 的办公室时候,这个办公室的员工会认真工作,并且这个办公室的员工通知所有办公室编号是 i 的倍数的办公室,通知他们老板来了,让他们认真工作。因此,可怜检查完第 i 个办公室的时候,所有编号是 i 的倍数(包括 i )的办公室的员工会认真工作。

可怜发现了员工们通风报信的行为,她发现,对于每种不同的顺序 p ,都存在一个最小的 t(p) ,使得可怜按照这个顺序检查完前 t(p) 个办公室之后,所有的办公室都会开始认真工作。她把这个 t(p) 定义为 p 的检查时间。

可怜想知道所有 t(p) 的和。

但是这个结果可能很大,她想知道和对 10^9+7 取模后的结果。

输入格式

第一行输入两个整数 l,r 表示编号范围,题目中的 n 就是 r-l+1

输出格式

一个整数,表示所有 t(p) 的和。

样例

样例输入

2 4

样例输出

16

样例解释

考虑所有办公室被检查的相对顺序:

  • 2 3 4,时间是 2
  • 3 2 4,时间是 2
  • 4 2 3,时间是 3
  • 4 3 2,时间是 3
  • 2 4 3,时间是 3
  • 3 4 2,时间是 3

和是 16

大样例见附加文件。

数据范围与提示

对于 20\% 的数据, r-l+1\leq 8
对于另 10\% 的数据, l=1
对于另 10\% 的数据, l=2
对于另 30\% 的数据, l\leq 200
对于 100\% 的数据, 1\leq l\leq r\leq 10^7