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

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:`
`ACEBDADBECBDACEBDAECBECADCADBECAEBDCEADBCEBDADACEBDBEACDBECAEBDACECADB14 modulo 11 = 3So the answer is 3.  `
• Number of test-cases is 28.