烤串串

烤串串

题目描述

在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

信息

ID
1010
难度
4
分类
(无)
标签
递交数
1
已通过
1
通过率
100%
被复制
2
上传者