描述
Akahashi 君定义相邻元素互质的排列是好的，于是他给你n,p,让你求出长度为n的好的排列的个数 。
输入格式
一行，两个数n,p.
输出格式
一行，表示答案 mod p.
输入： 4 114514 输出： 12样例解释
合法的排列有：
(1, 2, 3, 4)
(1, 4, 3, 2)
(2, 1, 3, 4)
(2, 1, 4, 3)
(2, 3, 1, 4)
(2, 3, 4, 1)
(3, 2, 1, 4)
(3, 4, 1, 2)
(4, 1, 2, 3)
(4, 1, 3, 2)
(4, 3, 1, 2)
(4, 3, 2, 1)
样例2
输入：
15 123456
输出：
6336
数据范围 对于所有数据，有 n ≤ 28，10^7 ≤ p ≤ 10^9。 注意样例中的 p 并不满⾜该数据范围。
特别的，本题有 28 组数据，对于第 i 组数据，保证 n = i。
对于 i ≤ 20，测试点 i 的分数为 2，对于 i > 20 ，其分数为 i − 17。
为了加快评测速度，对于 i > 1，测试点 i 依赖于测试点 i − 1。