P13561 "WWOI R1" WsW's Pens

WsW is planning to give some pens to bln.

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

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

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

### Sample $1$ Explanation |Plan|Given labels|Kept labels| |:-:|:-:|:-:| |$1$|$2$|None| |$2$|None|$2$| There are $2$ different excellent pen-giving plans in total. ### Sample $2$ Explanation |Plan|Given labels|Kept labels| |:-:|:-:|:-:| |$1$|$1$|$2,3,4$| |$2$|$1,2$|$3,4$| |$3$|$1,4$|$2,3$| |$4$|$1,2,4$|$3$| |$5$|$3$|$1,2,4$| |$6$|$2,3$|$1,4$| |$7$|$3,4$|$1,2$| |$8$|$2,3,4$|$1$| 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}$. | Subtask ID | $a,b\leq$ | Special Property | Score | | :-: | :-: | :-: | :-: | | $1$ | $20$ | None | $10$ | | $2$ | $10^3$ | None | $10$ | | $3$ | $10^5$ | B | $5$ | | $4$ | $10^5$ | None | $10$ | | $5$ | $7\times10^6$ | A | $5$ | | $6$ | $7\times10^6$ | B | $5$ | | $7$ | $7\times10^6$ | None | $15$ | | $8$ | $10^{18}$ | A | $5$ | | $9$ | $10^{18}$ | B | $10$ | | $10$ | $10^{18}$ | None | $25$ | - Special Property A: $a\times k>b$. - Special Property B: $k=2$. Translated by ChatGPT 5