33833번 - Gładkie permutacje 다국어

Ciąg $p_1, p_2, \dots , p_k$ nazwiemy:

• rosnącym, jeśli $p_1 < p_2 < \dots < p_k$;
• malejącym, jeśli $p_1 > p_2 > \dots > p_k$;
• wypukłym, jeśli dla pewnego $1 ≤ l ≤ k$ ciąg $p_1, p_2, \dots , p_l$ jest rosnący, a ciąg $p_l , p_{l+1}, \dots , p_k$ jest malejący.

W szczególności ciąg jednoelementowy uznajemy zarówno za rosnący, malejący i wypukły.

Permutację nazwiemy $(a, b, c)$-gładką, jeśli spełnione są jednocześnie trzy warunki:

• najdłuższy jej podciąg rosnący jest długości $a$,
• najdłuższy jej podciąg malejący jest długości $b$,
• najdłuższy jej podciąg wypukły jest długości $c$.

Na przykład permutacja $4$, $5$, $2$, $3$, $1$ jest $(2, 3, 4)$-gładka, gdyż:

• jej najdłuższy podciąg rosnący to na przykład $4$, $5$;
• jej najdłuższy podciąg malejący to na przykład $4$, $2$, $1$;
• jej najdłuższy podciąg wypukły to na przykład $4$, $5$, $3$, $1$.

Masz dane trzy liczby całkowite $a$, $b$, $c$ spełniające $1 ≤ a ≤ b ≤ c < a + b$ oraz liczbę pierwszą $p$. Można udowodnić, że dla takiej trójki $a$, $b$, $c$ zbiór wszystkich $(a, b, c)$-gładkich permutacji jest niepusty i skończony. Napisz program, który wyznaczy:

• długość najdłuższej permutacji $(a, b, c)$-gładkiej (oznaczmy ją przez $n$),
• resztę z dzielenia przez $p$ liczby $(a, b, c)$-gładkich permutacji długości $n$.

W jedynym wierszu wejścia są cztery liczby całkowite $a$, $b$, $c$, $p$ ($1 ≤ a ≤ 20$, $a ≤ b ≤ 50\, 000$, $b ≤ c < a + b$, $10^7 ≤ p ≤ 10^9$), oznaczające odpowiednio: maksymalne długości ciągów rosnących, malejących, wypukłych w rozpatrywanych permutacjach, oraz liczbę pierwszą $p$.

W jedynym wierszu wyjścia powinny znaleźć się dwie liczby całkowite: długość najdłuższej permutacji $(a, b, c)$-gładkiej oraz liczba permutacji $(a, b, c)$-gładkich tej długości modulo $p$.

Wyjaśnienie przykładów: Zbiór wszystkich $(2, 2, 3)$-gładkich permutacji jest następujący:

• $1$, $3$, $2$
• $2$, $3$, $1$
• $2$, $1$, $4$, $3$
• $2$, $4$, $1$, $3$
• $3$, $1$, $4$, $2$
• $3$, $4$, $1$, $2$

Najdłuższe $4$ z nich mają długość $4$.

W drugim teście przykładowym rozważamy $(2, 3, 3)$-gładkie permutacje długości $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$