#include<bits/stdc++.h>
using namespace std;
long long MOD=1e9+7;
vector<vector<long long> > multiply(vector<vector<long long> > a,vector<vector<long long> > b)
{
int i,j,k;
int r1=a.size();
int r2=b.size();
int c1=a[0].size();
int c2=b[0].size();
vector<vector<long long> > c(r1,vector<long long> (c2));
for(i=0;i<r1;i++)
{
for(j=0;j<c2;j++)
{
for(k=0;k<r2;k++)
{
c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;
}
}
}
return c;
}
vector<vector<long long> > pow(vector<vector<long long> > a,long long n)
{
if(n==0)
{
//will not go here;
return a;
}
if(n==1)
return a;
vector<vector<long long> > b=pow(a,n/2);
b=multiply(b,b);
if(n%2)
b=multiply(a,b);
return b;
}
long long eval(long long n,vector<vector<long long> > a,vector<vector<long long> > b)
{
if(n==0)
return 1;
else
{
vector<vector<long long> > d=pow(a,n);
d=multiply(d,b);
long long sum=0;
for(int i=0;i<d.size();i++)
sum+=d[i][0];
return sum%MOD;
}
}
long long solve()
{
int M,x,y,sz,c=0;
cin>>M;
cin>>x>>y;
sz=(M+1)/2;
int mat[25][25]={{0}};
int count=(sz*(sz+1))/2;
int i,j;
for(i=1;i<=sz;i++)
{
for(j=1;j<=i;j++)
{
mat[i][j]=c++;
}
}
for(i=1;i<=sz;i++)
{
for(j=i+1;j<=sz;j++)
{
mat[i][j]=mat[j][i];
}
}
for(i=1;i<=sz;i++)
{
for(j=sz+1;j<=M;j++)
{
mat[i][j]=mat[i][M+1-j];
}
}
for(i=sz+1;i<=M;i++)
{
for(j=1;j<=M;j++)
{
mat[i][j]=mat[M+1-i][j];
}
}
/*cout<<"Matrix\n";
for(i=1;i<=M;i++)
{
for(j=1;j<=M;j++)
cout<<mat[i][j]<<" ";
cout<<endl;
}
cout<<endl;
*/
vector<vector<long long> > a(count,vector<long long > (count));
vector<vector<long long> > b(count,vector<long long> (1));
b[mat[x][y]][0]=1;
vector<pair<int,int> > ar(8);
c=0;
int all[3]={-1,1,0};
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
if(all[i]==all[j] && all[i]==0)
continue;
ar[c++]=make_pair(all[i],all[j]);
}
}
// for(int i=0;i<8;i++)
// cout<<ar[i].first<<" "<<ar[i].second<<endl;
c=0;
for(int i=1;i<=sz;i++)
{
for(int j=1;j<=i;j++)
{
for(int k=0;k<8;k++)
{
x=i+ar[k].first;
y=j+ar[k].second;
if(x>=1 && y>=1 && x<=M && y<=M)
a[mat[x][y]][c]++;
}
c++;
}
}
/*
for(i=0;i<a.size();i++)
{
for(j=0;j<a[0].size();j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
for(i=0;i<b.size();i++)
{
for(j=0;j<b[0].size();j++)
cout<<b[i][j]<<" ";
cout<<endl;
}
*/
int N;
cin>>N;
//cout<<"\nAns=";
return eval(N,a,b);
}
int main()
{ //cout<<"MOD "<<MOD<<endl;
freopen("in09.txt","r",stdin);
//freopen("out09.txt","w",stdout);
int t;
cin>>t;
while(t--)
{
cout<<solve()<<endl;
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmxvbmcgbG9uZyBNT0Q9MWU5Kzc7CgoKdmVjdG9yPHZlY3Rvcjxsb25nIGxvbmc+ID4gbXVsdGlwbHkodmVjdG9yPHZlY3Rvcjxsb25nIGxvbmc+ID4gYSx2ZWN0b3I8dmVjdG9yPGxvbmcgbG9uZz4gPiBiKQogewogCWludCBpLGosazsKIAlpbnQgcjE9YS5zaXplKCk7CiAJaW50IHIyPWIuc2l6ZSgpOwogCWludCBjMT1hWzBdLnNpemUoKTsKIAlpbnQgYzI9YlswXS5zaXplKCk7CiAJCiAJdmVjdG9yPHZlY3Rvcjxsb25nIGxvbmc+ID4gYyhyMSx2ZWN0b3I8bG9uZyBsb25nPiAoYzIpKTsKIAlmb3IoaT0wO2k8cjE7aSsrKQogCSAgewogCSAgCWZvcihqPTA7ajxjMjtqKyspCiAJICAJICB7CiAJICAJICAJZm9yKGs9MDtrPHIyO2srKykKIAkgIAkgIAkgIHsKIAkgIAkgIAkgIAljW2ldW2pdPShjW2ldW2pdK2FbaV1ba10qYltrXVtqXSklTU9EOwogCSAgCSAgCSAgfQogCSAgCSAgfQogCSAgfQogCXJldHVybiBjOwogfQoKdmVjdG9yPHZlY3Rvcjxsb25nIGxvbmc+ID4gcG93KHZlY3Rvcjx2ZWN0b3I8bG9uZyBsb25nPiA+IGEsbG9uZyBsb25nIG4pCiAgewogIAlpZihuPT0wKQogIAkgIHsKICAJICAJLy93aWxsIG5vdCBnbyBoZXJlOwogIAkgIAlyZXR1cm4gYTsKICAJICB9CiAgCWlmKG49PTEpCiAgCSAgcmV0dXJuIGE7CiAgCSAgCiAgCXZlY3Rvcjx2ZWN0b3I8bG9uZyBsb25nPiA+IGI9cG93KGEsbi8yKTsKICAJYj1tdWx0aXBseShiLGIpOwogIAlpZihuJTIpCiAgCSAgYj1tdWx0aXBseShhLGIpOwogIAlyZXR1cm4gYjsKICB9CmxvbmcgbG9uZyBldmFsKGxvbmcgbG9uZyBuLHZlY3Rvcjx2ZWN0b3I8bG9uZyBsb25nPiA+IGEsdmVjdG9yPHZlY3Rvcjxsb25nIGxvbmc+ID4gYikKIHsKIAlpZihuPT0wKQogICAJICByZXR1cm4gMTsKICAgCWVsc2UKICAgCSAgewogICAJICAJdmVjdG9yPHZlY3Rvcjxsb25nIGxvbmc+ID4gZD1wb3coYSxuKTsKICAgCSAgCWQ9bXVsdGlwbHkoZCxiKTsKICAgCSAgCWxvbmcgbG9uZyBzdW09MDsKICAgCSAgCWZvcihpbnQgaT0wO2k8ZC5zaXplKCk7aSsrKQogICAJICAJICBzdW0rPWRbaV1bMF07CiAgIAkgIAlyZXR1cm4gc3VtJU1PRDsKICAgCSAgfQogfQoKCmxvbmcgbG9uZyBzb2x2ZSgpCnsKCWludCBNLHgseSxzeixjPTA7CgljaW4+Pk07CgljaW4+Png+Pnk7Cglzej0oTSsxKS8yOwoJaW50IG1hdFsyNV1bMjVdPXt7MH19OwoJaW50IGNvdW50PShzeiooc3orMSkpLzI7CglpbnQgaSxqOwoJZm9yKGk9MTtpPD1zejtpKyspIAoJewoJCWZvcihqPTE7ajw9aTtqKyspIAoJCSAgewoJCSAgCW1hdFtpXVtqXT1jKys7CgkJICB9Cgl9CiAgIAlmb3IoaT0xO2k8PXN6O2krKykgCgl7CgkJZm9yKGo9aSsxO2o8PXN6O2orKykgCgkJICB7CgkJICAJbWF0W2ldW2pdPW1hdFtqXVtpXTsKCQkgIH0KCX0KCWZvcihpPTE7aTw9c3o7aSsrKQoJIHsKCSAJZm9yKGo9c3orMTtqPD1NO2orKykKCSAJIHsKCSAJIAltYXRbaV1bal09bWF0W2ldW00rMS1qXTsKCSAJIH0KCSB9CiAgIAoJZm9yKGk9c3orMTtpPD1NO2krKykKCSB7CgkgCWZvcihqPTE7ajw9TTtqKyspCgkgCSB7CgkgCSAJbWF0W2ldW2pdPW1hdFtNKzEtaV1bal07CgkgCSB9CgkgfQoJIC8qY291dDw8Ik1hdHJpeFxuIjsKCSBmb3IoaT0xO2k8PU07aSsrKQoJICB7CgkgIAlmb3Ioaj0xO2o8PU07aisrKQoJICAJICBjb3V0PDxtYXRbaV1bal08PCIgIjsKCSAgCWNvdXQ8PGVuZGw7CgkgIH0KCSAgY291dDw8ZW5kbDsKICAgKi8KICAgdmVjdG9yPHZlY3Rvcjxsb25nIGxvbmc+ID4gYShjb3VudCx2ZWN0b3I8bG9uZyBsb25nID4gKGNvdW50KSk7CiAgIHZlY3Rvcjx2ZWN0b3I8bG9uZyBsb25nPiA+IGIoY291bnQsdmVjdG9yPGxvbmcgbG9uZz4gKDEpKTsKICAgCiAgIGJbbWF0W3hdW3ldXVswXT0xOwogICB2ZWN0b3I8cGFpcjxpbnQsaW50PiA+IGFyKDgpOwogICBjPTA7CiAgIGludCBhbGxbM109ey0xLDEsMH07CiAgIGZvcihpbnQgaT0wO2k8MztpKyspCiAgICB7CiAgICAJZm9yKGludCBqPTA7ajwzO2orKykKICAgIAkgIHsKICAgIAkgIAlpZihhbGxbaV09PWFsbFtqXSAmJiBhbGxbaV09PTApCiAgICAJICAJICBjb250aW51ZTsKICAgIAkgIAkgIAogICAgCSAgCSBhcltjKytdPW1ha2VfcGFpcihhbGxbaV0sYWxsW2pdKTsKICAgIAkgIH0KICAgIH0KICAvLyBmb3IoaW50IGk9MDtpPDg7aSsrKQogICAgLy8gY291dDw8YXJbaV0uZmlyc3Q8PCIgIjw8YXJbaV0uc2Vjb25kPDxlbmRsOwogICAgYz0wOwogICBmb3IoaW50IGk9MTtpPD1zejtpKyspCiAgICB7CiAgICAJZm9yKGludCBqPTE7ajw9aTtqKyspCiAgICAJICB7CiAgICAJICAJZm9yKGludCBrPTA7azw4O2srKykKICAgIAkgIAkgewogICAgCSAgCSAJeD1pK2FyW2tdLmZpcnN0OwogICAgCSAgCSAJeT1qK2FyW2tdLnNlY29uZDsKICAgIAkgIAkgCWlmKHg+PTEgJiYgeT49MSAmJiB4PD1NICYmIHk8PU0pCiAgICAJICAJIAkgICBhW21hdFt4XVt5XV1bY10rKzsKICAgIAkgIAkgCSAgIAogICAgCSAgCSB9CiAgICAJICAJYysrOwogICAgCSAgfQogICAgfQogICAvKgogICBmb3IoaT0wO2k8YS5zaXplKCk7aSsrKQoJICB7CgkgIAlmb3Ioaj0wO2o8YVswXS5zaXplKCk7aisrKQoJICAJICBjb3V0PDxhW2ldW2pdPDwiICI7CgkgIAljb3V0PDxlbmRsOwoJICB9CiAgIGZvcihpPTA7aTxiLnNpemUoKTtpKyspCgkgIHsKCSAgCWZvcihqPTA7ajxiWzBdLnNpemUoKTtqKyspCgkgIAkgIGNvdXQ8PGJbaV1bal08PCIgIjsKCSAgCWNvdXQ8PGVuZGw7CgkgIH0KICAgKi8KICAgaW50IE47CiAgIGNpbj4+TjsKICAgLy9jb3V0PDwiXG5BbnM9IjsKICAgcmV0dXJuIGV2YWwoTixhLGIpOwp9CgppbnQgbWFpbigpCnsgLy9jb3V0PDwiTU9EICI8PE1PRDw8ZW5kbDsKZnJlb3BlbigiaW4wOS50eHQiLCJyIixzdGRpbik7Ci8vZnJlb3Blbigib3V0MDkudHh0IiwidyIsc3Rkb3V0KTsKCWludCB0OwoJY2luPj50OwoJd2hpbGUodC0tKQoJIHsKCSAJY291dDw8c29sdmUoKTw8ZW5kbDsKCSAJCgkgfQp9Cg==