该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题目描述】

Farmer John 的 n 头奶牛排成一队去参加了一个活动。

由于在来时路上，有些相邻的奶牛发生了一些不愉快。

所以回去时，John 要把奶牛重新排队，使得每一头奶牛都不与来时相邻的奶牛再相邻了。

问：John 有多少种不同的重新排队方案？

你能帮助 John 吗？答案可能很大，你只需要输出其除以 m 的余数即可。

【输入格式】

一行，包含两个正整数 n, m。

【输出格式】

一行，一个整数，表示答案除以 m 的余数。

【样例1输入】

4 123

【样例1输出】

2

【样例1解释】

假设来时队伍从队头到队尾的奶牛编号分别为 1, 2, 3, 4，则回去时有以下两种排队方案：

2,4,1,3

3,1,4,2

【样例2输入】

777 7777777

【样例2输出】

3055481

【数据范围】

20% 的数据，1 ≤ n ≤ 10

100% 的数据，1 ≤ n ≤ 1000, 1 ≤ m ≤ 10^9