{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e .sampledata { font-family: \"Courier New\", Courier, monospace; white-space: pre; }\u003c/style\u003e\u003cp\u003e\u0026nbsp;我们知道,从区间[L,H](L和H为整数)中选取N个整数,总共有(H-L+1)^N种方案。小z很好奇这样选出的数的最大公约数的规律,他决定对每种方案选出的N个整数都求一次最大公约数,以便进一步研究。然而他很快发现工作量太大了,于是向你寻求帮助。你的任务很简单,小z会告诉你一个整数K,你需要回答他最大公约数刚好为K的选取方案有多少个。由于方案数较大,你只需要输出其除以1000000007的余数即可。\u003c/p\u003e \n\u003cdiv\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e输入一行,包含4个空格分开的正整数,依次为N,K,L和H。\u003c/p\u003e \n\u003cdiv\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e输出一个整数,为所求方案数。\u003c/p\u003e \n\u003cdiv\u003e\u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cspan class\u003dsampledata\u003e2 2 2 4\u003c/span\u003e\u003c/div\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cspan class\u003dsampledata\u003e3\u003c/span\u003e\u003c/div\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e\u0026nbsp;样例解释\u003c/p\u003e\n\u003cbr\u003e \n\u003cdiv\u003e\n 所有可能的选择方案:(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4)\n\u003c/div\u003e\n\u003cbr\u003e \n\u003cdiv\u003e\n 其中最大公约数等于2的只有3组:(2, 2), (2, 4), (4, 2)\n\u003c/div\u003e\n\u003cbr\u003e \n\u003cdiv\u003e\n 对于100%的数据,1≤N,K≤10^9,1≤L≤H≤10^9,H-L≤10^5\n\u003c/div\u003e\n\u003cp\u003e\u003c/p\u003e"}}]}