Introduction

植发

一位萌新完成了和而不同，这是他痉挛产生的变化!

Runtime Error
检测到评测机失活，需要重启评测机
我们仅收到某些爆零信息，
然后为您重启电脑。
(-1226%)

错误信息：
CRITICAL_PROCESS_TIME_LIMIT_EXCEEDED

题目背景

因为《数学题》被骂了，所以这真的是一道数学题。

如果再被骂我就不会再碰数学了（确信）

题目描述

定义一个数列 \(a\) 为楼梯数列，当且仅当对于任意 \(i\) 满足 \(1\le i<n\)，有 \(a_{i+1}-a_i\ge k\)。

求有多少个长度为 \(n\) 的楼梯序列 \(a\) 满足：

• \(l\le a_1<a_2<......<a_n\le r\)

当然这题不可能这么简单，所以小 Y 的询问次数将等于痉挛里的楼梯个数。

输入格式

第一行一个正整数 \(T\) 表示询问数量。

接下来 \(T\) 行，每行四个正整数 \(n,l,r,k\) 表示一个楼梯。

输出格式

共 \(T\) 行，每行一个整数表示答案，对 \(1000003\) 取模。

样例

样例输入

5
3 2 6 1
2 1 5 2
3 1 5 2
3 1 5 3
5 10 40 3

样例输出

10
6
1
0
33649

提示

对于所有数据：

\(1\le T\le 10^5\)

\(1\le n\le 10^9\)

\(1\le l\le r\le 10^{16}\)

\(1\le k\le 10^6\)

注：YZB在模拟赛里被卡常卡到爆炸，所以他没有卡你。