The Tabtabitab cat is trying to understand how AI models work. So the cat is trying to build an AI model.  For each training run, the AI model selects a random hyperparameter between \(L\) and \(R\) for doing calculation. There is also a secret number \(x\). After doing some experiments, the cat found out that the model works best when the gcd of the selected hyperparameter \(p_i\), with the secret integer \(x\) is greater than \(1\). In other words, \(gcd(x, p_i) > 1\). The cat named this phenomenon a good draw.
Now, the big question: if Tabtabtab draws \(d\) hyperparameters in succession, what is the probability that each draw will be a good draw? Print the answer in modulo \(10^9 + 7\).
 

The first line contains \(T\) the number of test cases.
The line contains 4 integers \(L, R, x, d\).

\(1 \le T \le 10^4\)
\(1 \le L \le R \le 10^9\)
\(1 \le x \le 10^9\)
\(1 \le d \le 10 ^ 9\)

A single integer: the probability (modulo \(10 ^ 9 + 7\)) that all \(d\) picks satisfy \(gcd(x, p_i) > 1\)
 

Input copy	Output copy
1 5 7 4 1	333333336