Triangulacja

Triangulacja

Bajtoleusz, programista w firmie Bitosoft, otrzymał następujące zadanie. Dla danego wielokąta wypukłego o n wierzchołkach policz, ile jest jego triangulacji (podziałów na trójkąty) modulo m, składających się z dokładnie n - 2 trójkątów. Bajtoleusz bardzo wystraszył się zadania, ale po krótkich poszukiwaniach znalazł wzór na liczby Catalana. Wie, że jak policzy n-tą liczbę Catalana (C_n), to otrzyma odpowiedź dla wielokąta wypukłego o n + 2 wierzchołkach. Trójkąty w danej triangulacji mogą mieć wyłącznie takie wierzchołki, które pokrywają się z wierzchołkami danego wielokąta wypukłego.

Zadanie:

Napisz program, który:
• wczyta dwie liczby: n i m
• wyznaczy liczbę triangulacji modulo m, składających się z dokładnie n - 2 trójkątów, wielokąta o n wierzchołkach.
• wypisze wynik na standardowe wyjście

Wejście:

W pierwszej linii znajdują się dwie liczby całkowite: n i m (3 <= n <= 1000000; 2 <= m <= 10⁹). Liczba m jest pierwsza.

Wyjście:

Jedna liczba, będąca liczbą triangulacji modulo m, składających się z dokładnie n - 2 trójkątów, wielokąta o n wierzchołkach.

Przykład:

wejście:
5 3

wyjście:
2

Wyjaśnienie przykładu: