#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
ll m , x , y , n ;
ll MOD = 1e9+7 ;
void create_sym_matrix( vector< vector<ll> > &sym_matrix , ll len ) {
//cout << "creating symmetric matrix" << endl ;
int counter = 0 ;
//marking relevent cells with unique numbers...
for( int i = 1 ; i <= len ; i++ )
for( int j = 1 ; j <= i ; j++ )
sym_matrix[i][j] = counter++ ;
//copying remaining half as symmetry suggests that...
for( int i = 1 ; i <= len ; i++ )
for( int j = i+1 ; j <= len ; j++ )
sym_matrix[i][j] = sym_matrix[j][i] ;
for( int i = 1 ; i <= len ; i++ )
for( int j = len+1 ; j <= m ; j++ )
sym_matrix[i][j] = sym_matrix[i][m-j+1] ;
for( int i = len+1 ; i <= m ; i++ )
for( int j = 1 ; j <= m ; j++ )
sym_matrix[i][j] = sym_matrix[m-i+1][j] ;
//cout << "created symmetric matrix" << endl ;
//for( int i = 1 ; i <= m ; i++ ) {for( int j = 1 ; j <= m ; j++ ) cout << sym_matrix[i][j] << " " ; cout << endl ; }
}
void set_answer_matrix( vector< vector< ll > > &answer_matrix , vector< vector< ll > > sym_matrix , int len ) {
//cout << "setting answer matrix" << endl ;
int a , b , column = 0 ;
for( int i = 1 ; i <= len ; i++ )
for( int j = 1 ; j <= i ; j++ ) {
for( int k = -1 ; k <= 1 ; k++ )
for( int l = -1 ; l <= 1 ; l++ ){
if( !k && !l ) ;
else {
a = i+k ; b = j+l ;
if( a < 1 || a > m || b < 1 || b > m ) ;
else {
//cout << a << " , " << b << " , sm: " << sym_matrix[a][b] << " , cl: " << column << endl ;
answer_matrix[ sym_matrix[a][b] ][column]++ ;
}
}
}
column++ ;
}
//cout << "set answer matrix" << endl ;
//for( int i = 0 ; i < column ; i++ ) {for( int j = 0 ; j < column ; j++ ) cout << answer_matrix[i][j] << " " ; cout << endl ; }
}
vector< vector< ll > > multiply(vector< vector< ll > > a , vector< vector< ll > > b)
{
int i,j,k;
int r1=a.size() , r2=b.size();
int c1=a[0].size() , c2=b[0].size();
vector< vector< ll > > c(r1 , vector< ll >(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< ll > > power( vector< vector< ll > > a, ll n)
{
if( n==1 )
return a;
vector< vector< ll > > b=power(a,n/2);
b=multiply(b,b);
if(n&1)
b=multiply(a,b);
return b;
}
ll calculate_answer( ll n , vector< vector< ll > > answer_matrix , vector< vector< ll > > sym_matrix )
{
vector< vector< ll > > resultant_matrix =power( answer_matrix , n );
ll sum=0;
for(int i=0 ; i< resultant_matrix.size() ; i++)
sum+=resultant_matrix[i][ sym_matrix[x][y] ];
return sum%MOD;
}
typedef long long ll ;
int main() {
int t ;
cin >> t ;
while( t-- ) {
//input taken...
cin >> m >> x >> y >> n ;
assert( 1 <= m <= 20 ) ;
assert( 1 <= x <= m && 1 <= y <= m ) ;
assert( 1 <= n <= 1e9 ) ;
ll len = (m+1)>>1 ;
ll moves = len*(len+1)/2 ;
vector< vector< ll > > sym_matrix(m+1, vector<ll>(m+1) ) ;
create_sym_matrix( sym_matrix , len);
vector< vector< ll > > answer_matrix( moves , vector< ll >(moves) ) ;
set_answer_matrix( answer_matrix , sym_matrix , len ) ;
ll answer = calculate_answer( n , answer_matrix , sym_matrix ) ;
assert( 0 <= answer < 1e9-1 ) ;
cout << answer << endl ;
}
return 0 ;
}