$\color{red}\texttt{Z}\color{orange}\texttt{B}\color{green}\texttt{O}\color{cyan}\texttt{J}\color{black}-\texttt{P1005}$

$\texttt{Cyn's Question}$

$\texttt{Description}$

某 $\texttt{hs}$ 成功见到了小 $\texttt{C}$ ，并向她说出了心中的那三个字。不过，众所周知，小 $\texttt{C}$ 是个很傲娇的姑娘，她听了某 $\texttt{hs}$ 的表白后，说：“你如果能回答出我的这个问题，我就接受你的表白。”同志们，行动起来，为了某 $\texttt{hs}$ 的幸福而奉献出一份脑力吧！

小 $\texttt{C}$ 给出了这样一个问题：有一个长度为 $n$ 的有序数列 $A$ ，对于每个 $A$ 中的元素，满足且 $A_i\in [1,m]$ 且 $A_i\in N_+$ ，求问：

一，对于给定的区间 $[L,R]$ ，对每个在区间中的正整数 $k$ ，总共有多少个数列 $A$ 满足

gcd(A_i)(i=1,2,\cdot\cdot\cdot,n)=k

二，对于给定的区间 $[L,R]$ ，对每个在区间中的正整数 $k$ ，总共有多少个数列 $A$ 满足

k|lcm(A_i)(i=1,2,\cdot\cdot\cdot,n)

其中 $1\leq L\leq R\leq m$ 恒成立。

$\texttt{Input Format}$

第一行两个数 $T,type$ ，表示子问题的数量和这些子问题的类型。后 $T$ 行每行四个数 $n,m,L,R$ ，描述了每个子问题。

$\texttt{Output Format}$

共 $T$ 行，每行一个整数，分别表示每个子问题的答案，每个答案请对 $10^9+7$ 取模。

$\texttt{Sample}$

$\texttt{Input 1}$

$\texttt{Output 1}$


xxxxxxxxxx
3125
34
3
2
1

$\texttt{Input 2}$

$\texttt{Output 2}$


xxxxxxxxxx
12310
9185
6303
4202
2101

$\texttt{Input 3}$


xxxxxxxxxx
1 1
22 27 1 1

$\texttt{Output 3}$


xxxxxxxxxx
603941223

$\texttt{Hint}$

对于前 $50\%$ 的数据，满足 $type=1,n,m\leq10^7,T\leq 10$ 。

对于后 $50\%$ 的数据，满足 $type=2,n,m\leq10^3,T\leq 500$ 。