台大 ICPC 傳奇強隊的一大支柱蛋餅，在休假期間去日本玩耍。
在東大裡面購買紀念品的時候，忽然看見傳奇強者 marooonrk 在東大合作社留下的謎語：

Jlyhq wzr 0 vhtxhqfh D, E ri ohqjwk Q.
Rphohw fdq gr wkh iroorzlqj rshudwlrq dw prvw N wlphv.

1. Slfn wzr lqwhjhu O, U.
2. iru doo l vxfk wkdw O <= l <= U: dgg rqh wr hlwkhu D_l ru E_l

Qrz kh zrqghu, krz pdqb gliihuhqw uhvxowv fdq kh pdgh iurp deryh frqvwuxfwlrq.
Qrwlfh wkdw wzr uhvxowv duh frqvlghuhg gliihuhqw li dqg rqob li wkhuh lv vrph l vxfk wkdw D_l != D'_l ru E_l != E'_l

在 crytpo 也是一大支柱的蛋餅，很快的就了解了題目的意思：

給定兩個長度為 $N$ 的序列 $A, B$，一開始 $A_i = B_i = 0(1 \le i \le N)$。
接下來蛋餅可以做以下操作至多 $K$ 次

1. 選定一個區間 $[L, R] $$(1 \le L \le R \le N)$
2. 對於 $i$ 從 $L$ 到 $R$，將 $A_i$ 加一或是將 $B_i$ 加一。 注意到每個 $i$ 都可以分別決定要選擇 $A$ 序列或是 $B$ 序列。

最後，蛋餅會按照順序將 $A_1,A_2,A_3,\ldots,A_N,B_1,B_2,B_3,\ldots,B_N$ 印在一張白紙上。

請問用上述的方法，總共能夠製造出多少種不同的白紙呢？

（兩張白紙被視為不同若且唯若存在 $i$ 使得白紙上面的 $A_i \ne A'_i$ 或是 $B_i \ne B'_i$ ）

因為答案實在是太大了，請輸出答案除以 $M$ 的餘數即可。