题目描述

前不久，探险队前往 inst 沙漠进行考察。他们在沙漠中发现了一种生命力十分强悍的植物。这种植物从种子到发芽只需要 \(1\) 天时间，而从发芽的第 \(x\) 天开始，一直到第 \(y\) 天（包括第 \(y\) 天），每天又都会繁殖出一粒种子，每棵植物都会在发芽的第 \(z\) 天时枯萎死亡。因为探险队以前在营地里并没有见过这种植物，于是他们取了一颗种子放在他们的营地里（这一天叫做第 \(0\) 天），他们想知道第 \(n\) 天的时候营地里这种神奇的植物(不包括种子)的棵数 \(m\)。但是这个数太大了，他们现在只想知道 \(m\) 对 \(10007\) 的余数。

格式

输入格式

第一行为正整数 \(t(≤5)\)，表示数据组数；接下来每行包含四个正整数 \(x,y,z,n\)，其中 \(x≤y<z≤2500，n≤2500\)。

输出格式

对于每组数据，输出 \(m\) 对 \(10007\) 的余数。

样例1

样例输入1

2
1 2 3 4
105 207 305 485

样例输出1

5
129

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T1\)

文件IO

freopen("plant.in","r",stdin);
freopen("plant.out","w",stdout);