测试数据来自 b6e0_OJ/1010

题目描述

在Ducati的校门口有一个小摊子，专门卖烤串串。
细心的Ducati发现，小摊子是由\(4\)种肉组成的；形象地称为A,B,C和D；该小摊上任何一个串串的肉片数总为\(n\)。
同时Ducati也发现，小摊子的师傅为了让顾客更多，要使串串不再单调。即，他连起来的串串满足下面的条件:
1. 经过0次或多次交换两个在不同位置的肉片，不可能出现三个连续的肉片使得它们从上到下分别为A形肉片,B形肉片和C形肉片；
2. 这一次卖的串串与之前任何一次卖的串串不完全相同(即相同位置上肉片的种类一样)。
于是，Ducati想知道，这位师傅最多能够卖多少个烤串串。

输入格式

输入仅一行\(n\)和\(mod\)，为一根串串上肉片的数量与模数。

输出格式

输出师傅最多可卖的烤串串的数量对模数取模的值。

输入输出样例1

输入

3 31

输出

27

输入输出样例2

输入

100 998244353

输出

935966213

样例解释

对于第一个样例：
这里仅有\(6\)个长度为\(3\)的串串得不到:
1.ABC 2.ACB 3.BAC 4.BCA 5.CAB 6.CBA。
所以答案就是\(4^3-6=58\)。由于答案需要对31取模，所以应该输出\(58\bmod31=27\)。

数据范围

对于100%的数据，\(1\le n\le10^6\)
Subtask 1(20%): \(n\le10\)。
Subtask 2(30%): \(n\le1000\)。
Subtask 3(50%): 无特殊限制。

贡献者

题面，数据: b6e0
核题: Ducati