MP3 Player

Time limit2sMemory limit1024 MB

Summary

Count the permutations of 1 to n where no two consecutive numbers are adjacent, and output the count modulo m.

Level: Medium6 of 10
Topics: Combinatorics, Dynamic programming, Prefix sum
Solved: No attempts yet

Statement

Vasya recently bought a new MP3 player, doPi Shuffle. Unlike every other player Vasya has used, it has a "shuffle" function that randomizes the playlist order.

Vasya loaded $n$ of his favorite songs onto the player. He had listened to them on his computer for a long time, so he remembers their playlist order very well.

The player put the songs in a random order. After playing the playlist several times, Vasya noticed that no two songs that were adjacent in the old playlist are adjacent in the new one. He wants to know how often this kind of arrangement is possible.

Number the songs from 1 to $n$ in the order they appear in the playlist on the computer. Write a program that counts the number of ways to rearrange the songs so that no two songs with consecutive numbers are next to each other. Since this number can be large, output it modulo $m$ .

Input

The input file contains two integers $n$ and $m$ ( $2 \le n \le 2000$ , $2 \le m \le 10^9$ ).

Output

Output the number of valid arrangements modulo $m$ .

Examples2

Example 1
Input
```
2 1000000
```
Expected output
```
1
```
Example 2
Input
```
5 1000000
```
Expected output
```
53
```