Triangulation

Time limit1sMemory limit32 MB

Summary

Given n and m, compute the sum of triangulation counts T_3 + ... + T_n of convex polygons, reduced modulo m.

Level: Medium7 of 10
Topics: Combinatorics, Math, Number theory, Dynamic programming
Solved: No attempts yet

Problem

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$ .

Input

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$ )

Output

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

Examples3

Example 1
Input
```
5 1000
```
Expected output
```
8
```
Example 2
Input
```
4 1000000000
```
Expected output
```
3
```
Example 3
Input
```
6 1000000000
```
Expected output
```
22
```