最大公约数

题目描述

给定 �, �, �, �，请问有多少整数数组 �1 , �2 , . . . , �� 满足 1 ≤ �� ≤ � 1 ≤ � ≤ � 并且 这 � 个数的最大公约数 ��� ∈ �, � 。由于答案可能很大，请输出答案 mod 1�9 + 7。

输入格式 一行四个整数 �, �, �, �。

输出格式 一行一个整数表示答案。

样例输入 1 5 5 1 5

样例输出 1 3125

样例输入 2 5 5 4 5

样例输出 2 2

样例输入输出 3 见下发文件。

数据规模 共 10 组数据。

测试点 1,2 满足 �, � ≤ 8。

测试点 3,4,5 满足 �, � ≤ 500。

测试点 6,7 满足 � = � = 1。

对于所有数据，满足 1 ≤ �, � ≤ 106 , 1 ≤ � ≤ � ≤ �。