問題一覧 > 通常問題

No.1241 Eternal Tours

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 16
作問者 : hitonanodehitonanode / テスター : hos.lyrichos.lyric
22 ProblemId : 5076 / 出題時の順位表
問題文最終更新日: 2020-09-08 18:25:12

問題文

あなたは南北方向に $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$ 回の行動のしかたを数えます.これを全て挙げると,

  • (東,東,西)
  • (東,西,東)
  • (東,何もしない,何もしない)
  • (何もしない,東,何もしない)
  • (何もしない,何もしない,東)
の $5$ 通りです.(西,東,東)や(北,南,東)等の行動は途中で都市の外にはみ出してしまうため禁止されることに気を付けてください.

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。