（未完结）“文远知行杯”GDET第十四届竞赛（网络赛共10题，仅整理出6题）

#include <iostream>
#include <cstdio>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))using namespace std;const int mod=;
const int maxn=4e4+;
long long fio[maxn]={,};
long long sum[maxn]={,};void make_table()
{
for(int i=; i<maxn; i++)
{
fio[i]=(fio[i-]+fio[i-])%mod;
sum[i]=(fio[i]*fio[i])% mod+sum[i-];
//后面是要求 sum的差值，这里的sum不要求余，可大致看一下也能发现long long 不会溢出
}
}int main()
{
make_table();
/*
for(int i=0; i<10; i++)
{
printf("%d %I64d %I64d\n", i , fio[i], sum[i]);
}
*/
int Q;
while(cin>>Q)
{
while(Q--)
{
int a,b,c,d;
cin>>a>>b>>c>>d;
a=a*+b+;
c=c*+d+;
b=max(a,c);
d=min(a,c);
cout<<(sum[b]-sum[d-])%mod<<endl;
//取余别忘记了
}
} return ;
}