You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

（喜）

题目描述

一个序列 $S$ 是 Accepted 的，当且仅当满足以下性质：

• $|S| = N$；
• $\forall i \in [1, N]$，$S_i \in [L, R]$，$S_i \in \mathbb{N}$；
• $\tau \ge 1$；

给定 $N, L, R$，问有多少种不同的 Accepted 的序列，答案对 $1000003$ 取模。

其中：

• $|S|$：$S$ 的长度；
• $\forall$：对于所有；
• $\mathbb{N}$：非负整数集；
• $\tau$：满足以下条件的数对 $(i, j)$ 的数量：
  • $(i, j) \in [1, N]$，$(i, j) \in \mathbb{N^*}$；
  • $i < j$；
  • $S_j < S_i$。

输入

本题共有 $T$ 组测试数据，共输入 $T + 1$ 行。

• 第 $1$ 行：$1$ 个整数 $T$，表示测试数据数量。
• 第 $2 \sim T + 1$ 行，第 $q + 1$ 行表示第 $q$ 组测试数据。

对于每组测试数据：

• 输入 $3$ 个整数 $N,L,R$。

输出

共输出 $T$ 行：

• 第 $q$ 行：$1$ 个整数表示测试数据 $q$ 的答案。

样例

1
3 2 3

4

满足条件的序列如下：

• $\{2,3,2\}$，$\{3, 2, 2\}$，$\{3,2,3\}$，$\{3,3,2\}$。

数据范围

• 对于 $100\%$ 的数据，$11 \le T \le 104$，$1 \le N \le 10^{12}$，$1 \le L \le R \le 10^{12}$；
• 提示：你可以通过 $T$ 的个位数判断此测试点属于哪个 $\text{Subtask}$。