说明

本题不再提供附加样例文件。

题目描述

给出三个整数 n, a, b, 现在要构造一个整数数列 S，要求满足：

1、数列 S 至少包含一个元素，但不能超过 n 个元素。

2、数列 S 的元素 $S_i$ 满足 $a ≤ S_i ≤ b$

3、对于数列 S 中的元素，若 $i < j$ 则必有 $S_i ≤ S_j$

问：能构造出多少个不同的数列？

答案可能很大，你需要输出其 mod 1000003 的值。

输入格式

多组数据。

第一行：一个整数 T，表示数据组数。

接下来 T 行，每行包含三个整数 $n, a, b$。

输出格式

T 行，每行一个整数，表示对应数据的答案 mod 1000003。

输入样例

4
1 2 3
2 2 3
470348262 64822990 361270978
388237294 513695086 848021666

输出样例

2
5
727710
268379

样例解释

此处仅解释样例中第 2 组数据。满足条件的序列有 5 个:

2

3

2, 2

2, 3

3, 3

数据范围

100% 的数据：1 ≤ n, a, b ≤ 10^9, 1 ≤ T ≤ 100。数据保证 a ≤ b。