Background

WsW is planning to give some pens to bln.

Problem Description

WsW has $b-a+1$ pens. Each pen has a unique integer label in the range $a\sim b$. He decides to give some of the pens to bln and keep the rest for himself.

When all pens satisfy the following conditions, WsW considers the plan an excellent pen-giving plan:

• If the pen labeled $x$ is given to bln, then the pen labeled $x/k$ must be kept by WsW.
• If the pen labeled $x$ is kept by WsW, then the pen labeled $x/k$ must be given to bln.

Of course, these conditions only apply if WsW has a pen labeled $x/k$.

WsW believes that if a pen with some label is given away in one plan but kept in another plan, then these two pen-giving plans are different.

Now all pens have been labeled. WsW wants to know how many different excellent pen-giving plans there are in total.

Since the answer may be very large, you only need to output the total number of plans modulo $10^9+7$.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, which is the number of test cases.

Then follow $T$ test cases. Each test case is formatted as follows:

The first line contains a positive integer $k$.

The second line contains two positive integers $a,b$, which specify the range of pen labels.

Output Format

For each test case, output one line containing an integer, indicating the number of different excellent pen-giving plans. Output the answer modulo $10^9+7$.

1
2
2 2

2

1
3
1 4

8

1
114
514 1919810

532406817

Hint

Sample $1$ Explanation

There are $2$ different excellent pen-giving plans in total.

Sample $2$ Explanation

There are $8$ different excellent pen-giving plans in total.

Constraints

This problem uses bundled tests.

For all testdata, it is guaranteed that $1\le T\le 5$, $1\le a\le b\le 10^{18}$, $2\le k\le10^{5}$.

• Special Property A: $a\times k>b$.
• Special Property B: $k=2$.

Translated by ChatGPT 5