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

1N2,000                         The number of pots.

2M1,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 M-1 (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 test-cases is 28.


hide comments
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


Added by:Rofael Emil
Date:2010-10-26
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