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⁹+7 the number of sequences of integers A satisfying the following conditions:
1) A should contain exactly N elements.
2) L ≤ A₁ ≤ A₂ ≤ ... ≤ A_N ≤ 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⁹+7 in a separate line.

Constraints

1 ≤ T ≤ 100
1 ≤ N ≤ 100
1 ≤ L, R, X ≤ 10⁹