#P7017. [2017年成都七中集训]矩阵染色

    ID: 6848 传统题 1000ms 512MiB 尝试: 3 已通过: 2 难度: 7 上传者: 标签>难度分类提高+/省选-构造与建模差分转化线性代数与代数线性递推组合数学Pascal 递推数论费马小定理等比数列求和模逆元逆元线性递推快速幂二项式定理CF2300

[2017年成都七中集训]矩阵染色

矩阵染色(color)

题目描述

用 mm 种不同颜色给一个2行、若干列的矩阵染色,不要求全部颜色都使用。两个格子相邻,当且仅当有一条公共边;相邻格子的颜色必须不同。

设2行 ii 列矩阵的合法染色方案数为 f(i)f(i),求

∑i=1nf(i)(2i)m(modp)。\sum_{i=1}^{n}f(i)(2i)^m\pmod p。

输入格式

一行三个正整数 n,m,pn,m,p。

输出格式

输出所求答案。

样例输入1

2 5 100000007

样例输出1

266880

样例解释

m=5m=5 时,f(1)=20f(1)=20,f(2)=260f(2)=260,所以答案为

20⋅25+260⋅45=266880。20\cdot2^5+260\cdot4^5=266880。

数据范围

所有数据中的 pp 均为素数。

测试点 nn 上界 mm 上界 pp 上界
1—4 100000100000 10910^9
5—12 10910^9 100100
13—16 100000100000 10001000
17—20 10001000 10910^9