//Developer : ruhul1995 || Time : 00:58 AM ||Date : 23/11/2017
//how to optimize this code… i want the program to execute value of 10 power 6 and give the value for fibanacci and factorial…please help
#define MOD 1000000007
using namespace std;
const int MAX = 2 * 1000000;
long long int f[MAX] = {0};
long long int fib(long long int n)
{
/* Declare an array to store Fibonacci numbers. */
long long int f[n+1];
long long int i;
/* 0th and 1st number of the series are 0 and 1*/
f[0] = 1;
f[1] = 1;
for (i = 2; i <= n; i++)
{
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
long long int fact( long long int n)
{
if(n == 0 || n == 1)
return 1 ;
else
return n*fact(n-1);
}
int main()
{
int testcase;
cin>>testcase;
while(testcase--)
{
long long int n , m , k1 , i , p = 0 , final_answer = 0 ;
cin>>n>>m>>k1;
for( i = n ; i <= m ; i++)
{
p += fib(i) * fact(i) ;
}
// cout<<"p="<<p<<endl;
final_answer = p/k1 ; // x * k <= p
cout<<(final_answer % MOD)<<endl;
}
return 0;
}