Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

HS09WIE - Rooks

You are given a checkerboard from which some fields have been removed.

checkerboard 9x9

One is allowed to place pieces only on the grey fields (which lie on five diagonal lines). Johny is wondering in how many ways can he put N rooks on such a restricted chessboard of width N so that no two rooks stay on the same row or column.

Input

In the first and only line of input there are two numbers — N and M (4 ≤ N, M ≤ 10 000 000),
representing the width of the chessboard and a number modulo which you are to output the result.

Output

Output should contain only one number - the number of ways of placing the rooks, modulo M.

Example

Input:
4 1000
Output:
14

Scoring

By solving this problem you will score 10 points.


Added by:Adam Dzedzej
Date:2009-09-16
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TCL TEXT WHITESPACE
Resource:Thanks to Talent Association (www.talent.edu.pl)

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.