P13561 「WWOI R1」WsW 的笔

WsW 准备送几支笔给 bln。

WsW 有 $b-a+1$ 支笔，每支笔的编号为 $a\sim b$ 的正整数，且笔的编号互不相同。他决定送若干支笔给 bln，并将剩余的笔留给自己。 当所有的笔都满足以下条件时，WsW 认为这种送笔方案是**优秀送笔方案**： * 如果将编号为 $x$ 的笔送给 bln，那么必须将编号为 $x/k$ 的笔留给自己。 * 如果将编号为 $x$ 的笔留给自己，那么必须将编号为 $x/k$ 的笔送给 bln。 当然，这些条件的前提是 WsW 有编号为 $x/k$ 的笔。 WsW 认为，如果某个编号的笔在一种方案中被送出，在另一种方案中被留下，则这两种送笔方案是不同的。 现在所有的笔都已经被 WsW 编完号了，WsW 想知道一共有多少种**不同的优秀送笔方案**。 由于最后的结果可能很大，你只需要告诉 WsW 总方案数对 $10^9+7$ 取模后的值。

**本题有多组测试数据。** 输入的第一行包含一个正整数 $T$，表示数据组数。 接下来包含 $T$ 组数据，每组数据的格式如下： 第一行输入一个正整数 $k$。 第二行输入两个正整数 $a,b$，表示笔编号的范围。

对于每组数据：输出一行包含一个整数，表示有多少种**不同的优秀送笔方案**。答案对 $10^9+7$ 取模。

### 【样例 $1$ 解释】 |方案|送出编号|留下编号| |:-:|:-:|:-:| |$1$|$2$|无| |$2$|无|$2$| 共 $2$ 种不同的优秀送笔方案。 ### 【样例 $2$ 解释】 |方案|送出编号|留下编号| |:-:|:-:|:-:| |$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$| 共 $8$ 种不同的优秀送笔方案。 ### 【数据范围】 **本题采用捆绑测试**。 对于所有测试数据，保证 $1\le T\le 5$，$1\le a\le b\le 10^{18}$，$2\le k\le10^{5}$。 | 子任务编号 | $a,b\leq$ | 特殊性质 | 分值 | | :-: | :-: | :-: | :-: | | $1$ | $20$ | 无 | $10$ | | $2$ | $10^3$ | 无 | $10$ | | $3$ | $10^5$ | B | $5$ | | $4$ | ^ | 无 | $10$ | | $5$ | $7\times10^6$ | A | $5$ | | $6$ | ^ | B | $5$ | | $7$ | ^ | 无 | $15$ | | $8$ | $10^{18}$ | A | $5$ | | $9$ | ^ | B | $10$ | | $10$ | ^ | 无 | $25$ | * 特殊性质 A：$a\times k>b$。 * 特殊性质 B：$k=2$。