Hanadi has N flower pots each with a unique flower. The pots are arranged along in a line.

One day, She decided to change their order under the condition that no two pots that were originally next to each other remain next to each other.

Task

Write a program that is given the number of pots, calculates the number of possible orders satisfying the condition modulo a given integer M.

Input

• Line 1 contains the integer N, the number of flower pots.
• Line 2 contains the integer M.

Output

A single line containing one integer between 0 and M-1 (inclusive): the number of possible orders modulo M.

Constraints

1 ≤ N ≤ 2,000

2 ≤ M ≤ 1,000,000,000

Number of test cases is 28.

Example

Input:
5
11

Output:
3

Explanation

For 5 pots, there are 14 orders satisfying Hanadi's condition, assuming the original order of pots was "ABCDE", then the 14 possible orders are:

• ACEBD
• ADBEC
• BDACE
• BDAEC
• BECAD
• CADBE
• CAEBD
• CEADB
• CEBDA
• DACEB
• DBEAC
• DBECA
• EBDAC
• ECADB

14 modulo 11 = 3, so the answer is 3.

---

hide comments

	:D: 2019-07-18 03:29:37 SPOJ will run all test cases and give WA after that, even if the first one failed.
	redundant: 2015-09-01 11:05:43 giving WA after the last test case. please help. submission id 15034800
	Sagnik Mondal: 2015-08-29 14:00:47 please comment on the last test case??
	Gourav Saha: 2013-11-06 17:10:52 which datatype should be used in c?
	Gourav Saha: 2013-10-25 14:32:30 what is the last case? failing for the last case
	Priyanka Dusija: 2012-10-12 21:10:20 What is the last test case?
	Zhouxing Shi: 2012-07-16 01:55:35 great!
	Pranay: 2011-12-25 17:49:52 the range of N is > 1600 sorry It's 2000 not 1600 Last edit: 2011-12-25 17:49:10
	Rofael Emil: 2011-12-25 17:49:52 Constraints Updated 1 ≤ N ≤ 1,600 The number of pots. 2 ≤ M ≤ 1,000,000,000