Problem: GLA Smooth permutations [A] Potyczki Algorytmiczne 2025, round five. Limits: 1024 MB, 3 s. 14.03.2025

We call a sequence $p_1, p_2, \dots, p_k$: increasing, if $p_1 < p_2 < \dots < p_k$; decreasing, if $p_1 > p_2 > \dots > p_k$; * convex, if for some $1 \le l \le k$ the sequence $p_1, p_2, \dots, p_l$ is increasing, and the sequence $p_l, p_{l+1}, \dots, p_k$ is decreasing.

In particular, a single-element sequence is considered increasing, decreasing, and convex. A permutation is called $(a, b, c)$-smooth if three conditions are satisfied simultaneously: its longest increasing subsequence has length $a$, its longest decreasing subsequence has length $b$, * its longest convex subsequence has length $c$.

For example, the permutation $4, 5, 2, 3, 1$ is $(2, 3, 4)$-smooth, because: its longest increasing subsequence is, for example, $4, 5$; its longest decreasing subsequence is, for example, $4, 2, 1$; * its longest convex subsequence is, for example, $4, 5, 3, 1$.

You are given three integers $a, b, c$ satisfying $1 \le a \le b \le c < a + b$ and a prime number $p$. It can be proven that for such a triple $a, b, c$, the set of all $(a, b, c)$-smooth permutations is non-empty and finite. Write a program that determines: the length of the longest $(a, b, c)$-smooth permutation (let us denote it by $n$), the remainder of the number of $(a, b, c)$-smooth permutations of length $n$ when divided by $p$.

Input

The single line of input contains four integers $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$), representing the maximum lengths of increasing, decreasing, and convex subsequences in the considered permutations, and the prime number $p$, respectively.

Output

The single line of output should contain two integers: the length of the longest $(a, b, c)$-smooth permutation and the number of $(a, b, c)$-smooth permutations of that length modulo $p$.

Examples

For the input:

2 2 3 10000019

the correct result is:

4 4

For the input:

2 3 3 999999937

the correct result is:

5 10

For the input:

8 9 11 15872567

the correct result is:

57 57

Note

Explanation of examples: The set of all $(2, 2, 3)$-smooth permutations is as follows: 1, 3, 2; 2, 3, 1; 2, 1, 4, 3; 2, 4, 1, 3; 3, 1, 4, 2; 3, 4, 1, 2

The longest 4 of them have length 4.

In the second example test, we consider $(2, 3, 3)$-smooth permutations of length 5:

3, 2, 1, 5, 4; 3, 2, 5, 1, 4; 4, 2, 1, 5, 3; 4, 2, 5, 1, 3; 4, 3, 1, 5, 2 4, 3, 5, 1, 2; 5, 2, 1, 4, 3; 5, 2, 4, 1, 3; 5, 3, 1, 4, 2; 5, 3, 4, 1, 2

Subtasks

In tests worth a certain non-zero number of points, the condition $c = a + b - 1$ holds.