O Delete 01s

制限時間: 2 sec メモリ制限: 1024 MB

Delete 01s

Statement

正整数 \(A, B, K\) および素数 \(P\) が与えられます。

\(A\) 個の \(0\) と \(B\) 個の \(1\) からなる長さ \(A+B\) の \(01\) 列を \(K\) 個作り、それらを \(x_1, x_2, \dots, x_K\) とします（順番も区別します）。あり得るすべての \((x_1, x_2, \dots, x_K)\) に対する以下の値の総和を \(P\) で割ったあまりを求めてください。

以下の条件を満たす \(01\) 列 \(S\) の転倒数としてあり得る最小値
- \(k=1,2,\dots,K\) の順に以下の操作をちょうど \(1\) 回ずつ行うことができる。
  - \(S\) の \(l\) 文字目から \(r\) 文字目までを取り出した部分文字列が \(x_k\) と一致するような整数 \(l, r~(1 \leq l \leq r \leq |S|)\) を選び、\(S\) の \(l\) 文字目から \(r\) 文字目までを削除する。

Input

入力は以下の形式で標準入力から与えられます。

\(A~B~K~P\)

入力は以下の制約をすべて満たします。

\(1 \leq A, B\)
\(A+B \leq 6666\)
\(1 \leq K \leq 2 \times 10^5\)
\(998244353 \leq P \leq 1.01 \times 10^9\)
\(A, B, K, P\) は正整数
\(P\) は素数

Output

答えを \(1\) 行で出力してください。

Scoring

以下の追加制約を満たすデータセットに正解した場合、部分点が与えられます。

(10点): \(A = B = K = 1\)
(30点): \(A+B \leq 150\)
(60点): 追加の制約はありません。

Examples

Input 1

3 1 2 998244353

Output 1

Input 2

13 17 25 1000000007

Output 2

900218392

Input 3

37 100 31415 1000000009

Output 3

580724348

Note

\(1\) つ目のテストケースについて、\((x_1, x_2) = (0010, 0100)\) のとき、下記より \(S = 00010100\) は条件を満たすことがわかります。

\(k=1\) : \((l, r) = (2, 5)\) を選び、\(S = 0100\) とする。
\(k=2\) : \((l, r) = (1, 4)\) を選び、\(S\) を空文字列とする。

サンプル