小强的积木

定义整数序列 $f$ 如下：

• $f(1)=1$，$f(2)=3$，$f(3)=12$，$f(4)=51$；
• 对任意 $n\ge 5$，有 $$f(n)=7f(n-1)-14f(n-2)+11f(n-3)-2f(n-4)。$$

给定正整数 $N$ 和质数 $P$，求 $f(N)$ 对 $P$ 取模后的非负余数。

输入格式

输入两个正整数 $N$ 和 $P$，其中 $P$ 保证为质数。

输出格式

输出一个整数，表示 $f(N)\bmod P$ 的非负余数。

样例输入

3 997

样例输出

12

样例解释

根据定义，$f(3)=12$，因此输出 $12$。

数据范围

• $N\le 10^9$；
• $P\le 10^8$；
• $N$ 和 $P$ 均为正整数，且 $P$ 为质数。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

3 997

输出

12