Background

Description

定义一个长度为 $n$ 的 $01$ 序列 $a$ 是合法的当且仅当：

• $a_1=a_n=0$。
• 不存在两个连续的 $1$。

小 C 希望对这个序列进行一些变换，一次变换的具体形式如下：

• 选择序列中的一个 $0$，并将其修改为 $1$。

小 C 希望变换后的序列满足如下条件：

• 序列仍然合法。
• 再对任意一个可变换位置（如果有）进行变换，序列都会不合法。

小 C 希望在此基础上最小化变换次数，并在最小化变换次数的基础上，统计有几种变换方案，并把方案数记作序列 $a$ 的权值 $f(a)$。两种变换方案不同当且仅当变换后的序列不同。

特别的，若 $a$ 不合法，则 $f(a)=0$。

现在，给定序列 $a$ 的长度 $n$，求 $\sum f(a)$ 对 $p$ 取模后的结果。

Format

Input

一行两个正整数 $n,p$，同题意。

Output

一行一个正数，表示答案。

Samples

3 1000000007

2

154147 1000000007

30911724

Limitation

对于 $100\%$ 的数据，$1\le n\le 10^{18}$，$10^9\leq p\leq 1.1\times 10^9,p\equiv1\pmod2$。各子任务的约束如下表所示：