問題一覧 > 通常問題

No.1241 Eternal Tours

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 30
作問者 : 👑 hitonanode / テスター : hos.lyric
お気に入りにしたユーザー ProblemId : 5076 / 自分の提出
問題文最終更新日: 2022-04-26 01:29:41
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
yukicoder contest 267 (順位表) の他の問題:

Problem Statement

You are in a city divided into a grid of $2^X - 1$ cells in the north-south direction and $2^Y - 1$ cells in the east-west direction, consisting of $(2^X - 1)(2^Y - 1)$ blocks in total. Initially, you are staying in the block that is $a$-th from the north and $b$-th from the west. You repeat the following $T$ times: choose one of the actions below and perform it.

  • Do nothing.
  • Move to the adjacent block immediately to the south.
  • Move to the adjacent block immediately to the north.
  • Move to the adjacent block immediately to the east.
  • Move to the adjacent block immediately to the west.
However, any action whose move would take you outside this city is forbidden.

Among the sequences of $T$ actions, find the number of those in which, in the final state, you are staying in the block that is $c$-th from the north and $d$-th from the west, and output it modulo $998244353$.

Input

$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$
  • All inputs are integers.

Output

Output the integer that is the answer. Print a newline at the end.

Sample

Sample 1
Input
1 2 3 1 1 1 2
Output
5

Initially, you are staying in the westernmost block of a city extending $(2^1 - 1 = )\, 1$ block north-south and $(2^2 - 1 = ) \, 3$ blocks east-west. We count the ways of performing $3$ actions such that you are staying in the central block after the sequence of actions. Listing all of them, there are the following $5$ ways:

  • (East, East, West)
  • (East, West, East)
  • (East, Do nothing, Do nothing)
  • (Do nothing, East, Do nothing)
  • (Do nothing, Do nothing, East)
Note that action sequences such as (West, East, East) and (North, South, East) are forbidden, because they would take you outside the city along the way.

Sample 2
Input
2 2 4 1 3 2 2
Output
28

Initially, you are staying in the northeasternmost block of a city extending $3$ blocks north-south and $3$ blocks east-west. We count the ways of performing $4$ actions such that you are staying in the central block after the sequence of actions. There are $28$ such ways; for example, (West, South, South, North) and (Do nothing, Do nothing, South, West) are among them.

Sample 3
Input
9 9 10 4 5 511 320
Output
0

Sample 4
Input
5 4 1000000000000000000 31 1 1 15
Output
578577990

Be careful of overflow with the value of $T$ given as input.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。