题目描述

前不久，探险队前往 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);