题目背景

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
2
2 2

2

1
3
1 4

8

1
114
514 1919810

532406817

提示

【样例 $1$ 解释】

方案	送出编号	留下编号
$1$	$2$	无
$2$	无	$2$

共 $2$ 种不同的优秀送笔方案。

【样例 $2$ 解释】

方案	送出编号	留下编号
$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$
$3$	$10^5$	B	$5$
$4$	^	无	$10$
$5$	$7\times10^6$	A	$5$
$6$	^	B
$7$		无	$15$
$8$	$10^{18}$	A	$5$
$9$	^	B	$10$
$10$		无	$25$

• 特殊性质 A：$a\times k>b$。

• 特殊性质 B：$k=2$。