No.1241 Eternal Tours
タグ : / 解いたユーザー数 28
作問者 : 👑
hitonanode
/ テスター :
👑 
hos.lyric
問題文
あなたは南北方向に $2^X - 1$ 個，東西方向に $2^Y - 1$ 個のマス目状に区切られた，全部で $(2^X - 1)(2^Y - 1)$ 個の区画からなる都市にいます．はじめ，あなたは北から $a$ 個目，西から $b$ 個目の区画に滞在しています．あなたは，以下の行動からいずれか一つを選び実行することを $T$ 回繰り返します．
- 何もしない．
- すぐ南の隣接する区画に移動する．
- すぐ北の隣接する区画に移動する．
- すぐ東の隣接する区画に移動する．
- すぐ西の隣接する区画に移動する．
一連の $T$ 回の行動のしかたのうち，特に最終状態においてあなたが北から $c$ 個目，西から $d$ 個目の区画に滞在しているようなものが何通りあるかを求め， $998244353$ で割った余りを出力してください．
入力
$X$ $Y$ $T$ $a$ $b$ $c$ $d$
- $1 \le X \le 17$
- $1 \le Y \le 17$
- $X + Y \le 18$
- $1 \le T \le 10^{18}$
- $1 \le a \le 2^X - 1$
- $1 \le b \le 2^Y - 1$
- $1 \le c \le 2^X - 1$
- $1 \le d \le 2^Y - 1$
- 入力はすべて整数
出力
答えとなる整数を出力してください．最後に改行してください．
サンプル
サンプル1
入力
1 2 3 1 1 1 2
出力
5
初期状態で，南北に $(2^1 - 1 = )\, 1$ 区画，東西に $(2^2 - 1 = ) \, 3$ 区画の広がりを持つ都市の最も西の区画に滞在しています．一連の行動後中央の区画に滞在しているような $3$ 回の行動のしかたを数えます．これを全て挙げると，
- （東，東，西）
- （東，西，東）
- （東，何もしない，何もしない）
- （何もしない，東，何もしない）
- （何もしない，何もしない，東）
サンプル2
入力
2 2 4 1 3 2 2
出力
28
初期状態で，南北に $3$ 区画，東西に $3$ 区画の広がりを持つ都市の最も北東の区画に滞在しています．一連の行動後中央の区画に滞在しているような $4$ 回の行動のしかたを数えます．このようなものは $28$ 通りあり，例えば（西，南，南，北）や（何もしない，何もしない，南，西）がこれに含まれます．
サンプル3
入力
9 9 10 4 5 511 320
出力
0
サンプル4
入力
5 4 1000000000000000000 31 1 1 15
出力
578577990
入力として与えられる $T$ の値のオーバーフローに気を付けてください．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。