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 109+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 109+7 in a separate line.
Constraints
1 ≤ T ≤ 100
1 ≤ N ≤ 100
1 ≤ L, R, X ≤ 109
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}.
