Busy Beaver 放棄了程式設計，決定轉而從事現代藝術！

Busy Beaver 有兩個帶有顏料的標記（tokens）。他想要用以下方式為一個無向圖上色：

• 最初，所有頂點皆未上色。首先，Busy Beaver 將一個標記放在頂點 1，另一個放在頂點 2。
• 接著，他沿著圖的邊滑動標記；每當一個頂點被標記覆蓋時，該頂點就會被上色。（注意：頂點 1 和 2 在開始時即已上色。）
• 如果存在一種方式可以將所有頂點上色，且在整個過程中兩個標記從未透過邊相連，則稱該圖為「藝術的」（artistic）。

請找出 $N$ 個頂點的藝術無向圖數量。由於答案可能很大，請輸出其對質數 $P$ 取模的結果。

輸入

輸入僅包含一行，包含兩個整數 $N$ 和 $P$ ($2 \le N \le 5000$; $5 \cdot 10^8 < P < 10^9$)。$P$ 為質數。

輸出

輸出 $N$ 個頂點的藝術無向圖數量，對 $P$ 取模。

範例

輸入格式 1

2 799999999

輸出格式 1

1

輸入格式 2

3 998244853

輸出格式 2

2

輸入格式 3

1984 998244853

輸出格式 3

424428556

Note

在第一個測試案例中，只有兩個頂點且沒有邊的圖是唯一的藝術圖。

在第二個測試案例中，下方的前兩個圖是藝術的。最後一個圖不是藝術的，因為無法將頂點 3 上色。