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