FLWRS  Flowers
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.
Constraints
1 ≤ N ≤ 2,000 The number of pots.
2 ≤ M ≤ 1,000,000,000
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 M1 (inclusive): the number of possible
orders modulo M.
Example
Input:
5
11
Output:
3
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.
 Number of testcases is 28.
hide comments
redundant:
20150901 11:05:43
giving WA after the last test case. please help. submission id 15034800 

Sagnik Mondal:
20150829 14:00:47
please comment on the


Gourav Saha:
20131106 17:10:52
which datatype should be used in c?


Gourav Saha:
20131025 14:32:30
what is the last case? failing for the last case 

Priyanka Dusija:
20121012 21:10:20
What is the last test case? 

Zhouxing Shi:
20120716 01:55:35
great! 

Pranay:
20111225 17:49:52
the range of N is > 1600


Rofael Emil:
20111225 17:49:52
Constraints Updated

Added by:  Rofael Emil 
Date:  20101026 
Time limit:  0.185s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  (modified) Egyptian Olympiad in Informatics ( EOI ) 2009, August 14  21, Cairo 