a-lcmer

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}.

Source: hackerearth | Difficulty: MEDIUM_HARD


Solutions: