UOJ Logo

NOI.AC

#81. 分数

统计

题目描述

老虎和蒜头是好朋友。

秋天到了,森林中学又迎来了一年一度的招生季。为了与科技时代接轨,森林中学今年即将使用全新的答题卡。只要考试时学生对答题卡进行规范性的填涂,考试后不用多久就能得到大家考试的成绩了。

然而,被聘请为顾问的老虎却犯了难。原来,在数学考试中,往往会出现如 $ \frac{2}{3}, 2 \sqrt 3 $ 这样的答案,而这样的答案在答题卡上没有填涂的方案——答题卡上只能够填涂在 $ 0 $ 至 $ 999 $ 之间的整数。于是老虎灵机一动,想出了一个绝妙的主意:如果答案是一个分数 $ \frac{x}{y} $ 的话,如果该分数已经不可约分,那么学生需要在答题卡上填涂 $ x + y $ ;否则,学生需要约分后再填涂。例如,答案为 $ \frac{4}{6} $ 时应该填涂 $ 5 $ ,而答案是 $ \frac{233}{1} $ 时应该填涂 $ 234 $ 。

不过,这样似乎并不能解决所有的问题,虽然答案是 $ \frac{1996}{2} $ 时可以填涂 $ 999 $ ,但答案是 $ \frac{1998}{2} $ 时应当填涂 $ 1000 $ ,但答题卡已经不允许填涂这么大的数字了。因此,在出题时一定要谨慎,避免这种情况的发生。

一天,老虎和蒜头聊起这事。于是蒜头产生了一个奇怪的问题:给定 $ A \le B, C \le D $ ,那么对于所有 $ A \le x \le B, C \le y \le D $ ,有多少分数 $ \frac{x}{y} $ 是可以被填涂进答题卡的?你现在的任务就是解决这样的问题。

输入格式

共一行四个正整数 $ A, B, C, D $ 。

输出格式

共一行一个整数,表示可以被填涂进答题卡的数字个数。由于答案可能很大,你只要输出其对 $ 10^9 + 7 $ 取模的答案即可。

样例

样例一

input

5 8 3 6

output

16

样例二

input

2018 2019 2018 2019

output

2

数据范围及限制

对于 100% 的数据,$ 1 \le A, B, C, D \le 10^{12}, A \le B, C \le D $ 。

对于 20% 的数据,$ 1 \le A, B, C, D \le 10 $ 。

对于 40% 的数据,$ 1 \le A, B, C, D \le 1000 $ 。

对于 60% 的数据,$ 1 \le (B - A + 1) \times (D - C + 1) \le 10^6 $ 。

对于另外 20% 的数据,$ 1 \le A, B, C, D \le 10^6 $ 。

时间限制: 1s

空间限制: 512MB