配るDP. 類別して状態をまとめる．
遷移する際，今いるマスと次のマスそれぞに対して，
(ゴールのマスと同じ行にいるか) \(\in 2\),
(ゴールのマスと同じ列にいるか) \(\in 2\)
の情報だけが重要． つまり，状態をまとめて減らすことができる．
注意:
行か列のうち，丁度一方しか動けない その場にとどまれないし，行と列を同時に動かすこともできない．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
vll h(2); ll k; cin >> h[0] >> h[1] >> k;
ll a,b,c,d; cin >> a >> b >> c >> d;
--a,--b,--c,--d;
dp[a==c][b==d] = 1;
rep(i,k){
swap(dp,old);
rep(f,2){ // flip
rep(t,2){
dp[0][t] += mint(h[f]-2)*old[0][t];
dp[1][t] += mint(1)*old[0][t];
dp[1][t] += mint(0)*old[1][t]; // 行と列，共に動かない というのは認めない
dp[0][t] += mint(h[f]-1)*old[1][t];
}
dp = TransposedMat(dp);
old = TransposedMat(old);
}
}
cout << dp[1][1].val() << endl;
return 0;
}
