P17339 【MX-X30-T5】メタモリボン

[メタモリボン - emon(Tes.) / 鏡音リン / MORE MORE JUMP！](https://www.bilibili.com/video/BV17S4y1D7fa)

考虑将一个非负整数集合中的所有元素的 $B$ 进制表示看作一个字符串集合。令 $R$ 的 $B$ 进制表示长度为 $l$，对于集合内的每个字符串，都在开头补 $0$ 直到其长度为 $l$。将这些字符串插入到一棵字典树中，并忽略字典树的边权与点的编号得到一棵**无权无标号**有根树。 给定 $B, L, R$，你需要统计所有非空的 $S \subseteq \{L, L + 1, L + 2, \dots, R\}$ 能得到的本质不同的树的数量，答案对 $10^9 + 7$ 取模。

本题有多测，第一行包含一个整数 $T$ 表示测试组数。 接下来 $T$ 行，表示每组测试的三个整数 $B,L,R$。

$T$ 行，每行输出一个整数，表示所有非空的 $S \subseteq \{L, L + 1, L + 2, \dots, R\}$ 能得到的本质不同的树的数量，答案对 $10^9 + 7$ 取模。

| 子任务编号 | 分数 | $T\le$ | $B\le$ | 特殊性质 | |:-:|:-:|:-:|:-:|:-:| | $1$ | $12$ | $5$ | $2$ | A | | $2$ | $12$ | $5$ | $2$ | 无 | | $3$ | $22$ | $10^4$ | $100$ | 无 | | $4$ | $5$ | $5$ | $10^9$ | B | | $5$ | $22$ | $5$ | $10^9$ | 无 | | $6$ | $12$ | $10^4$ | $10^9$ | A | | $7$ | $5$ | $10^4$ | $10^9$ | 无 | | $8$ | $10$ | $5\times 10^4$ | $10^9$ | 无 | 特殊性质 A：$L=0$。 特殊性质 B：$R-L\le 10$。 对于所有数据，$1 \le T \le 5 \times 10^4$，$2 \le B \le 10^9$，$0 \le L \le R \le 10^9$。