有一个长度为N的数组Ai,每个元素可以取1~M中的一个正整数。那么一共有M^N种可能的数组。因为 SHUXK 对数 论有特殊的爱好,所以他立刻想到了下面两个问题:
第一行包含两个正整数T和Type,分别表示测试数据的组数和数据类型 ( Type = 1时只询问 gcd 的问题, Type = 2时只询问 lcm 的问题)。 以下T行,每行包含四个正整数N,M,L,R( 1 ≤ L ≤ R≤ M),含义如题面所述。 T<=500,Type=1时,M<=10^7,Type=2时M<=1000
输出文件应包含T行,每行输出一个整数,表示一组测试数据的答案对 1,000,000,007取模的结果。答案的顺序应与输入数据的顺序保持一致。
5 1 5 5 1 5 5 5 2 5 5 5 3 5 5 5 4 5 5 5 5 5
3125 34 3 2 1