#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000007LL;
long long power( long long a, long long b)
{
long long ret = 1 ;
while ( b)
{
if ( b& 1 )
ret = ( ret * a) % mod;
a = ( a * a) % mod;
b / = 2 ;
}
return ( ret + mod) % mod;
}
long long inv( long long x)
{
return power( x, mod - 2 ) ;
}
int maxstep = 200 ;
long long grid[ 401 ] [ 401 ] ;
long long nextGrid[ 401 ] [ 401 ] ;
long long value[ 401 ] [ 401 ] ;
long long ans[ 401 ] ;
int dx[ ] = { 1 , - 1 , 0 , 0 } ;
int dy[ ] = { 0 , 0 , 1 , - 1 } ;
class RandomWalkOnGrid
{
public : int getExpectation( int x0, int y0, int t, int n, int m)
{
for ( int i = - maxstep; i <= maxstep; i++ )
for ( int j = - maxstep; j <= maxstep; j++ )
{
value[ i+ maxstep] [ j+ maxstep] = ( power( x0 + i, n) * power( y0 + j, m) ) % mod;
}
memset ( grid, 0 , sizeof ( grid) ) ;
memset ( ans, 0 , sizeof ( ans) ) ;
grid[ maxstep] [ maxstep] = 1 ;
for ( int c = 0 ; c <= maxstep; c++ )
{
memset ( nextGrid, 0 , sizeof ( nextGrid) ) ;
for ( int i = 0 ; i <= 2 * maxstep; i++ )
for ( int j = 0 ; j <= 2 * maxstep; j++ )
ans[ c] = ( ans[ c] + value[ i] [ j] * grid[ i] [ j] ) % mod;
if ( c < maxstep)
{
for ( int i = 0 ; i <= 2 * maxstep; i++ )
for ( int j = 0 ; j <= 2 * maxstep; j++ )
if ( grid[ i] [ j] > 0 )
for ( int dir = 0 ; dir < 4 ; dir ++ )
nextGrid[ i+ dx[ dir] ] [ j+ dy[ dir] ] = ( nextGrid[ i+ dx[ dir] ] [ j+ dy[ dir] ] + grid[ i] [ j] ) % mod;
for ( int i = 0 ; i <= 2 * maxstep; i++ )
for ( int j = 0 ; j <= 2 * maxstep; j++ )
grid[ i] [ j] = nextGrid[ i] [ j] ;
}
ans[ c] * = inv( power( 4 , c) ) ;
ans[ c] % = mod;
}
if ( t <= maxstep)
return ( ans[ t] * power( 4 , t) ) % mod;
else
{
long long ret = 0 ;
for ( int i = 0 ; i <= maxstep; i++ )
{
long long cur = ans[ i] ;
for ( int j = 0 ; j <= maxstep; j++ )
if ( j ! = i)
{
cur * = ( t - j + mod) % mod;
cur % = mod;
cur * = inv( ( i - j + mod) % mod) ;
cur % = mod;
}
ret + = cur;
ret % = mod;
}
return ( ret * power( 4 , t) ) % mod;
}
return - 1 ;
}
} ;
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpsb25nIGxvbmcgbW9kID0gMTAwMDAwMDAwN0xMOwoKbG9uZyBsb25nIHBvd2VyKGxvbmcgbG9uZyBhLCBsb25nIGxvbmcgYikKewoJbG9uZyBsb25nIHJldCA9IDE7Cgl3aGlsZShiKQoJewoJCWlmKGImMSkKCQkJcmV0ID0gKHJldCAqIGEpICUgbW9kOwoJCWEgPSAoYSAqIGEpICUgbW9kOwoJCWIgLz0gMjsKCX0KCXJldHVybiAocmV0ICsgbW9kKSAlIG1vZDsKfQoKbG9uZyBsb25nIGludihsb25nIGxvbmcgeCkKewoJcmV0dXJuIHBvd2VyKHgsIG1vZCAtIDIpOwp9CgppbnQgbWF4c3RlcCA9IDIwMDsKbG9uZyBsb25nIGdyaWRbNDAxXVs0MDFdOwpsb25nIGxvbmcgbmV4dEdyaWRbNDAxXVs0MDFdOwpsb25nIGxvbmcgdmFsdWVbNDAxXVs0MDFdOwpsb25nIGxvbmcgYW5zWzQwMV07CmludCBkeFtdID0gezEsIC0xLCAwLCAwfTsKaW50IGR5W10gPSB7MCwgMCwgMSwgLTF9OwoKY2xhc3MgUmFuZG9tV2Fsa09uR3JpZAp7CglwdWJsaWM6CWludCBnZXRFeHBlY3RhdGlvbihpbnQgeDAsIGludCB5MCwgaW50IHQsIGludCBuLCBpbnQgbSkKCXsKCQlmb3IoaW50IGkgPSAtbWF4c3RlcDsgaSA8PSBtYXhzdGVwOyBpKyspCgkJCWZvcihpbnQgaiA9IC1tYXhzdGVwOyBqIDw9IG1heHN0ZXA7IGorKykKCQkJewoJCQkJdmFsdWVbaSttYXhzdGVwXVtqK21heHN0ZXBdID0gKHBvd2VyKHgwICsgaSwgbikgKiBwb3dlcih5MCArIGosIG0pKSAlIG1vZDsKCQkJfQoJCW1lbXNldChncmlkLCAwLCBzaXplb2YoZ3JpZCkpOwoJCW1lbXNldChhbnMsIDAsIHNpemVvZihhbnMpKTsKCQlncmlkW21heHN0ZXBdW21heHN0ZXBdID0gMTsKCQlmb3IoaW50IGMgPSAwOyBjIDw9IG1heHN0ZXA7IGMrKykKCQl7CgkJCQoJCQltZW1zZXQobmV4dEdyaWQsIDAsIHNpemVvZihuZXh0R3JpZCkpOwoJCQlmb3IoaW50IGkgPSAwOyBpIDw9IDIqbWF4c3RlcDsgaSsrKQoJCQkJZm9yKGludCBqID0gMDsgaiA8PSAyKm1heHN0ZXA7IGorKykKCQkJCQlhbnNbY10gPSAoYW5zW2NdICsgdmFsdWVbaV1bal0gKiBncmlkW2ldW2pdKSAlIG1vZDsKCQkJCQoJCQlpZihjIDwgbWF4c3RlcCkKCQkJewoJCQkJZm9yKGludCBpID0gMDsgaSA8PSAyKm1heHN0ZXA7IGkrKykKCQkJCQlmb3IoaW50IGogPSAwOyBqIDw9IDIqbWF4c3RlcDsgaisrKQoJCQkJCQlpZihncmlkW2ldW2pdID4gMCkKCQkJCQkJCWZvcihpbnQgZGlyID0gMDsgZGlyIDwgNDsgZGlyICsrKQoJCQkJCQkJCW5leHRHcmlkW2krZHhbZGlyXV1baitkeVtkaXJdXSA9IChuZXh0R3JpZFtpK2R4W2Rpcl1dW2orZHlbZGlyXV0gKyBncmlkW2ldW2pdKSAlIG1vZDsKCQkJCQkJCQoJCQkJZm9yKGludCBpID0gMDsgaSA8PSAyKm1heHN0ZXA7IGkrKykKCQkJCQlmb3IoaW50IGogPSAwOyBqIDw9IDIqbWF4c3RlcDsgaisrKQoJCQkJCQlncmlkW2ldW2pdID0gbmV4dEdyaWRbaV1bal07CgkJCX0KCQkJYW5zW2NdICo9IGludihwb3dlcig0LCBjKSk7CgkJCWFuc1tjXSAlPSBtb2Q7CgkJfQoJCWlmKHQgPD0gbWF4c3RlcCkKCQkJcmV0dXJuIChhbnNbdF0gKiBwb3dlcig0LCB0KSkgJSBtb2Q7CgkJZWxzZQoJCXsKCQkJbG9uZyBsb25nIHJldCA9IDA7CgkJCWZvcihpbnQgaSA9IDA7IGkgPD0gbWF4c3RlcDsgaSsrKQoJCQl7CgkJCQlsb25nIGxvbmcgY3VyID0gYW5zW2ldOwoJCQkJZm9yKGludCBqID0gMDsgaiA8PSBtYXhzdGVwOyBqKyspCgkJCQkJaWYoaiAhPSBpKQoJCQkJCXsKCQkJCQkJY3VyICo9ICh0IC0gaiArIG1vZCkgJSBtb2Q7CgkJCQkJCWN1ciAlPSBtb2Q7CgkJCQkJCWN1ciAqPSBpbnYoKGkgLSBqICsgbW9kKSAlIG1vZCk7CgkJCQkJCWN1ciAlPSBtb2Q7CgkJCQkJfQoJCQkJcmV0ICs9IGN1cjsKCQkJCXJldCAlPSBtb2Q7CgkJCX0KCQkJcmV0dXJuIChyZXQgKiBwb3dlcig0LCB0KSkgJSBtb2Q7CgkJfQoJCXJldHVybiAtMTsKCX0KfTsK