---
title: An EZ Walking Problem
tags: problem
---

# An EZ Walking Problem

這是一個簡單的走路問題。

給一個 $N \times N$ 的網格圖， Kirby 一開始在 $(1,1)$，它一次可以往上下左右分別走不超過 $U,D,L,R$ 步（至少要走一步才算一次移動），一共會移動 $M$ 次，請問能使 Kirby 最後停在 $(N,N)$ 的方法數為多少？
（如果走到沒有辦法在移動了，但沒有走完 $M$ 次，不會算有走到 $(N,N)$）


## Intput

第一行有兩個正整數 $N, M$，表示網格圖的大小和要走幾次

第二行有四個非負整數 $U,D,L,R$，表示你一次最多可以往上下左右走多少步

- $2 \le N \le 10$
- $1 \le M \le 10^6$
- $0 \le U,D,L,R \le N-1$

## Ouput

輸出一個非負整數。由於答案可能會很大，請輸出 $\text{mod } 998244353$ 後的結果

## Subtask

本題共有五組子任務，條件限制如下所示。

| 子任務 | 分數 | 額外輸入限制 |
|:------:|:----:| ---------------------------- |
| 1 | 10 | $U=L=0$, $D=R=1$, $M = 2N-2$ |
| 2 | 13 | $M \le 5$ |
| 3 | 19 | $N = 2$ |
| 4 | 22 | $M \le 50000$ |
| 5 | 36 | 無額外限制 |

# Note

Zhu is very cute