Description

There are $n$ nodes forming a ring. For any positive integer $i \in [1, n]$, there is a bidirectional edge between $i$ and $(i \bmod n) + 1$.

There are two pieces, one black and one white. The white piece starts at node $x$, and the black piece starts at node $y$. Each second, both pieces move simultaneously: the white piece moves along one edge in the direction the black piece moved in the previous second (if both pieces were on the same node in the previous second, the white piece does not move), while the black piece can choose to move one edge in either direction or stay in place.

You are required to find the number of possible ways in which the two pieces never occupy the same node at the same time within $k$ seconds, modulo $998244353$.

In this problem, $n$ is odd.

Two ways are considered different if and only if there exists a moment when the movement direction of at least one piece differs between the two ways.

Input Format

Four integers $n, x, y, k$.

Output Format

A single integer representing the answer.

5 1 4 3

4

7 1 5 6

28

1145 141 919 810

783109298

Hint

Sample Explanation

For sample 1:

As shown in the figure, the white piece is at node $1$, and the black piece is at node $4$.

One possible way is:

• In the first second, the white piece moves to node $5$, and the black piece moves to node $3$.
• In the second second, the white piece moves to node $4$, and the black piece stays in place.
• In the third second, the white piece moves to node $3$, and the black piece moves to node $2$.

By enumerating all possibilities, it is easy to find that there are only four valid ways.

Data Range

This problem uses bundled testing.

For all data, $1 \leq n, k \leq 7 \times 10^3, 1 \leq x, y \leq n$.

Translated by ChatGPT 4.1