题目描述

花匠栋栋种了一排花，共 n 株，每株花都有自己的高度，第 i 株花的高度 $h_i$ 恰好为 i，即 $h_i$ = i。栋栋决定把这排花重新排放，希望排列得比较别致。

具体而言，栋栋希望下面条件能被满足：

条件：对于所有的 $1 < i < n$，有 $h_i > h_{i-1} 且 h_i > h_{i+1}$ 或 $h_i < h_{i-1} 且 h_i < h_{i+1}$；

请问，栋栋有多少种不同的排列方案？答案可能很大，你需要将其 mod m 后输出。

输入格式

一行，包含两个整数 $n$ 和 $m$，分别表示花的株数和模数。

输出格式

输出一行，包含一个整数，表示答案 mod m。

样例1输入

3 12

样例1输出

4

样例1解释

共 4 种方案：

1 3 2

2 1 3

2 3 1

3 1 2

样例2输入

4 3

样例2输出

1

样例2解释

共 10 种方案：

1 3 2 4

1 4 2 3

2 1 4 3

2 3 1 4

2 4 1 3

3 1 4 2

3 2 4 1

3 4 1 2

4 1 3 2

4 2 3 1

数据范围与提示

对于 20%的数据，满足 n≤10；

对于 40%的数据，满足 n≤20；

对于 70%的数据，满足 n≤555；

对于 100%的数据，满足 3≤n≤4321，m≤$10^9$