#include using namespace std; #if __has_include() #include using namespace atcoder; templateistream &operator>>(istream &is,static_modint &a){long long b;is>>b;a=b;return is;} istream &operator>>(istream &is,modint &a){long long b;cin>>b;a=b;return is;} #endif #ifdef LOCAL #include "debug.h" #else #define debug(...) static_cast(0) #define debugg(...) static_cast(0) templateostream &operator<<(ostream &os,const pair&p){os<; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templateistream &operator>>(istream &is,pair&p){is>>p.first>>p.second;return is;} templateistream &operator>>(istream &is,vector &a){for(auto &i:a)is>>i;return is;} templatevoid operator++(pair&a,int n){a.first++,a.second++;} templatevoid operator--(pair&a,int n){a.first--,a.second--;} templatevoid operator++(vector&a,int n){for(auto &i:a)i++;} templatevoid operator--(vector&a,int n){for(auto &i:a)i--;} #define reps(i,a,n) for(int i=(a);i<(n);i++) #define rep(i,n) reps(i,0,n) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcountll(x) #define fin(x) return cout<(0) ll myceil(ll a,ll b){return (a+b-1)/b;} template auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id(d,init)); else return init; } void SOLVE(); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout<>testcase; for(int i=0;i>x>>y>>t>>a>>b>>c>>d; a--,b--,c--,d--; vector>f(1<<(x+1),vector(1<<(y+1),0)); f[a][b]=1; f[(1<<(x+1))-2-a][b]=-1; f[a][(1<<(y+1))-2-b]=-1; f[(1<<(x+1))-2-a][(1<<(y+1))-2-b]=1; vector>g(1<<(x+1),vector(1<<(y+1),0)); g[0][0]=1; g[0][1]=1; g[1][0]=1; g[(1<<(x+1))-1][0]=1; g[0][(1<<(y+1))-1]=1; auto dft2d=[&](vector>&v)->void { rep(i,v.size())internal::butterfly(v[i]); int ny=v[0].size(); rep(j,ny){ vectortemp(v.size()); rep(i,v.size())temp[i]=v[i][j]; internal::butterfly(temp); rep(i,v.size())v[i][j]=temp[i]; } }; auto idft2d=[&](vector>&v)->void { int ny=v[0].size(); mint inv=mint(ny).inv(); rep(i,v.size()){ internal::butterfly_inv(v[i]); rep(j,ny)v[i][j]*=inv; } inv=mint(v.size()).inv(); rep(j,ny){ vectortemp(v.size()); rep(i,v.size())temp[i]=v[i][j]; internal::butterfly_inv(temp); rep(i,v.size())v[i][j]=temp[i]*inv; } }; dft2d(f); dft2d(g); rep(i,1<<(x+1))rep(j,1<<(y+1)){ f[i][j]*=g[i][j].pow(t); } idft2d(f); cout<