삼각분할

볼록 다각형의 삼각분할이란, 서로 교차하지 않는 대각선들을 이용해 다각형의 내부를 삼각형들로 나누는 것이다. 꼭짓점에는 $1$번부터 $N$번까지 번호가 붙어 있으며, 사용한 대각선의 집합이 서로 다르면 두 삼각분할은 다른 것으로 센다.

예를 들어 오각형을 삼각분할하는 방법은 모두 다섯 가지이다.

볼록 $n$각형을 삼각분할하는 방법의 수를 $T_n$이라고 할 때, $T_3 + T_4 + \cdots + T_n$의 값을 구하는 프로그램을 작성하시오.

첫째 줄에 두 정수 $n$과 $m$이 공백으로 구분되어 주어진다. ($3 \le n \le 100\,000$, $2 \le m \le 10^9$)

$T_3 + T_4 + \cdots + T_n$을 $m$으로 나눈 나머지를 출력한다.