[b6e0OJ]烤串串
测试数据来自 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
信息
- ID
- 1043
- 难度
- 4
- 分类
- (无)
- 标签
- 递交数
- 1
- 已通过
- 1
- 通过率
- 100%
- 上传者