High School Programming League Problems Archive

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

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.