数列 $p_1, p_2, \dots, p_k$ が以下を満たすとき、それぞれ次のように呼びます。 $p_1 < p_2 < \dots < p_k$ であるとき、増加列と呼ぶ。 $p_1 > p_2 > \dots > p_k$ であるとき、減少列と呼ぶ。 * ある $1 \le l \le k$ が存在し、数列 $p_1, p_2, \dots, p_l$ が増加列であり、かつ数列 $p_l, p_{l+1}, \dots, p_k$ が減少列であるとき、凸列と呼ぶ。

特に、要素数が1の数列は、増加列、減少列、および凸列のすべてであるとみなします。

ある順列が $(a, b, c)$-滑らかであるとは、以下の3つの条件を同時に満たすことを指します。 最長増加部分列の長さが $a$ である。 最長減少部分列の長さが $b$ である。 * 最長凸部分列の長さが $c$ である。

例えば、順列 $4, 5, 2, 3, 1$ は $(2, 3, 4)$-滑らかです。なぜなら： 最長増加部分列の例は $4, 5$ です。 最長減少部分列の例は $4, 2, 1$ です。 * 最長凸部分列の例は $4, 5, 3, 1$ です。

$1 \le a \le b \le c < a + b$ を満たす3つの整数 $a, b, c$ と素数 $p$ が与えられます。このような $a, b, c$ に対して、$(a, b, c)$-滑らかな順列の集合は空ではなく、有限であることが証明できます。

以下の値を求めるプログラムを作成してください。 最長の $(a, b, c)$-滑らかな順列の長さ（これを $n$ とします）。 長さ $n$ の $(a, b, c)$-滑らかな順列の個数を $p$ で割った余り。

入力

入力は1行で構成され、4つの整数 $a, b, c, p$ ($1 \le a \le 20, a \le b \le 50\,000, b \le c < a + b, 10^7 \le p \le 10^9$) が与えられます。これらはそれぞれ、考慮する順列における増加列、減少列、凸列の最大長、および素数 $p$ を表します。

出力

出力は1行で構成され、2つの整数を出力してください。最長の $(a, b, c)$-滑らかな順列の長さと、その長さを持つ $(a, b, c)$-滑らかな順列の個数を $p$ で割った余りです。

入出力例

入出力例 1

2 2 3 10000019

4 4

入出力例 2

2 3 3 999999937

5 10

入出力例 3

8 9 11 15872567

57 57

注記

例の解説：$(2, 2, 3)$-滑らかな順列の集合は以下の通りです。 $1, 3, 2 \quad 2, 3, 1 \quad 2, 1, 4, 3 \quad 2, 4, 1, 3 \quad 3, 1, 4, 2 \quad 3, 4, 1, 2$ これらの中で最も長いものは長さ4であり、4つ存在します。

2番目の例では、長さ5の $(2, 3, 3)$-滑らかな順列を考慮します。 $3, 2, 1, 5, 4 \quad 3, 2, 5, 1, 4 \quad 4, 2, 1, 5, 3 \quad 4, 2, 5, 1, 3 \quad 4, 3, 1, 5, 2$ $4, 3, 5, 1, 2 \quad 5, 2, 1, 4, 3 \quad 5, 2, 4, 1, 3 \quad 5, 3, 1, 4, 2 \quad 5, 3, 4, 1, 2$

小課題

ある一定の点数が与えられるテストケースでは、条件 $c = a + b - 1$ が成り立ちます。