Triangulation

A triangulation of a convex polygon divides its interior into triangles using diagonals that do not cross one another. The vertices are numbered from $1$ to $N$, and two triangulations are considered different whenever their sets of diagonals differ.

For example, a pentagon can be triangulated in exactly five ways.

Let $T_n$ be the number of ways to triangulate a convex $n$-gon. Write a program that computes $T_3 + T_4 + \cdots + T_n$.

The first line contains two integers $n$ and $m$, separated by a space. ($3 \le n \le 100\,000$, $2 \le m \le 10^9$)

Print the remainder of $T_3 + T_4 + \cdots + T_n$ divided by $m$.