P19137 [HackerEarth] You are given T test cases.
提高-
题目描述

You are given T test cases.
In each of them you are given four integers N, L, R and X.
Your task is to count modulo 10^9+7 the number of sequences of integers A satisfying the following conditions:
1) A should contain exactly N elements.
2) L ≤ A1 ≤ A2 ≤ ... ≤ AN ≤ R
3) the least common multiple of all numbers in A should be divisible by X.

Input format
The first line contains one integer number T, denoting the number of test cases.

Each of the next T lines contains four integers N, L, R, X.

Output format
For each test case find the answer and print it modulo 10^9+7 in a separate line.

Constraints
1 ≤ T ≤ 100
1 ≤ N ≤ 100
1 ≤ L, R, X ≤ 10^9

SAMPLE INPUT
2
2 1 7 6
1 1 50 7

SAMPLE OUTPUT
9
7

Explanation

In the first test case there are 9 sequences satisfying the given conditions: {1, 6}, {2, 3}, {2, 6}, {3, 4}, {3, 6}, {4, 6}, {5, 6}, {6, 6}, {6, 7}.

输入格式

见题面

输出格式

见题面

样例输入
100 99 77 999999919 223092870 99 73 999999952 735134400 97 100 999999941 223092870 97 31 999999977 735134400 97 76 999999996 223092870 96 100 999999960 735134400 98 89 999999904 223092870 98 41 999999933 735134400 100 16 999999912 223092870 98 63 999999984 735134400 96 24 999999910 223092870 96 23 999999945 735134400 98 34 999999932 223092870 100 52 999999985 735134400 96 57 999999916 223092870 98 29 999999970 735134400 99 66 999999999 223092870 99 18 999999975 735134400 99 81 999999906 223092870 98 25 999999939 735134400 96 93 1000000000 223092870 99 65 999999981 735134400 97 52 999999913 223092870 98 93 999999973 735134400 97 11 999999998 223092870 97 45 999999954 735134400 97 86 999999973 223092870 96 26 999999927 735134400 99 90 999999924 223092870 96 51 999999903 735134400 100 50 999999963 223092870 97 32 999999993 735134400 98 26 999999958 223092870 99 100 999999996 735134400 100 24 999999902 223092870 100 2 999999926 735134400 100 27 999999990 223092870 97 20 999999974 735134400 96 50 999999953 223092870 96 28 999999949 735134400 96 33 999999976 223092870 98 16 999999976 735134400 98 69 999999968 223092870 98 43 999999919 735134400 96 71 999999966 223092870 99 29 999999980 735134400 98 85 999999939 223092870 96 64 999999953 735134400 98 98 999999954 223092870 98 5 999999997 735134400 100 89 999999941 223092870 100 55 999999968 735134400 100 14 999999985 223092870 96 71 999999930 735134400 96 48 999999934 223092870 98 5 999999925 735134400 99 90 1000000000 223092870 98 1 999999995 735134400 100 33 999999921 223092870 97 12 999999943 735134400 100 60 999999995 223092870 100 87 999999930 735134400 96 85 999999919 223092870 98 83 999999918 735134400 100 36 999999985 223092870 98 35 999999971 735134400 97 67 999999936 223092870 96 78 999999937 735134400 97 10 999999921 223092870 98 48 999999915 735134400 100 43 999999919 223092870 99 39 999999943 735134400 97 60 999999914 223092870 99 65 999999938 735134400 99 42 999999977 223092870 100 17 999999910 735134400 98 41 999999932 223092870 96 51 999999937 735134400 98 100 999999919 223092870 99 88 999999910 735134400 98 47 999999998 223092870 96 35 999999994 735134400 100 24 999999912 223092870 100 13 999999942 735134400 99 88 999999964 223092870 96 28 999999967 735134400 99 97 999999972 223092870 99 64 999999984 735134400 97 28 999999908 223092870 100 7 999999944 735134400 96 29 999999921 223092870 98 68 999999922 735134400 97 8 999999937 223092870 100 77 999999987 735134400 100 23 999999907 223092870 98 70 999999972 735134400 98 34 999999908 223092870 97 76 999999984 735134400 97 3 999999986 223092870 99 13 999999901 735134400
样例输出
9 7 1 0 2 27 29 13 13 29 1810 100 5050 172 1001 398 100 149 139 1045 1134 72 0 0 1 31 0 1 1000 19342 4 1496 249 1 208083 218875 375250 334529633 933466176 1 791350 301 1086 10 36 886644294 1 495641523 763455847 617461961 969918313 0 834258250 0 140283902 770230907 2259714 696822959 466824728 592532885