TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3249
  • 题目
  • P3249【CQOI2015】选数
    限制 : 时间限制 : 10000 MS   空间限制 : 524288 KB
    问题描述

            我们知道,从区间[L,H](L和H为整数)中选取N个整数,总共有(H-L+1)N种方案。小z很好奇这样选出的数的最大公约数的规律,他决定对每种方案选出的N个整数都求一次最大公约数,以便进一步研究。然而他很快发现工作量太大了,于是向你寻求帮助。
            你的任务很简单,小z会告诉你一个整数K,你需要回答他最大公约数刚好为K的选取方案有多少个。由于方案数较大,你只需要输出其除以1000000007的余数即可。

    输入格式

            输入一行,包含4个空格分开的正整数,依次为N,K,L和H。

    输出格式

            输出一个整数,为所求方案数。

    样例输入

    2 2 2 4

    样例输出

    3

    提示

    样例解释
            所有可能的选择方案:(2,2), (2,3), (2,4), (3,2), (3,3), (3,4), (4,2), (4,3), (4,4)。
            其中最大公约数等于2的只有3组:(2,2), (2,4), (4,2)。

    数据范围
            对于30%的数据,N≤5,H-L≤5。
            对于100%的数据,1≤N,K≤109,1≤L≤H≤109,H-L≤105