#P1707. 刷题比赛

    ID: 739 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>递推倍增矩阵运算洛谷原创矩阵乘法线性递推递推式

刷题比赛

题目背景

nodgd 是一个喜欢写程序的同学,前不久洛谷 OJ 横空出世,nodgd 同学当然第一时间来到洛谷 OJ 刷题。
于是发生了一系列有趣的事情,他就打算用这些事情来出题恶心大家……

题目描述

洛谷OJ当然算是好地方,nodgd 同学打算和朋友分享一下。于是他就拉上了他的朋友 Ciocio 和 Nicole 两位同学一起刷题。喜欢比赛的他们当然不放过这样一次刷题比赛的机会!

在第 11 天 nodgd,Coicoi,Nicole 都只做了 11 道题。

在第 22 天 nodgd,Coicoi,Nicole 都只做了 33 道题。

他们都有着严格的刷题规则,并且会在每一天都很遵守规则的刷一定量的题。

1、nodgd 同学第 k+2k+2 天刷题数量

ak+2=pak+1+qak+bk+1+ck+1+rk2+tk+1a_{k+2}=pa_{k+1}+qa_k+b_{k+1}+c_{k+1}+rk^2+tk+1

2、Ciocio 同学第 k+2k+2 天刷题数量

bk+2=ubk+1+vbk+ak+1+ck+1+wkb_{k+2}=ub_{k+1}+vb_k+a_{k+1}+c_{k+1}+w^k

3、Nicole 同学第 k+2k+2 天刷题数量

$$c_{k+2} = xc_{k+1}+yc_k + a_{k+1} + b_{k+1} + z^k+k+2 $$

(以上的字母 p,q,r,t,u,v,w,x,y,zp,q,r,t,u,v,w,x,y,z 都是给定的常数,并保证是正整数)

于是他们开始了长时间的刷题比赛!一共进行了 nn

但是时间是可贵的,nodgd 想快速知道第 nn 天每个人的刷题数量。
不过 nodgd 同学还有大量的数学竞赛题、物理竞赛题、英语竞赛题、美术竞赛题、体育竞赛题…… 要做,就拜托你来帮他算算了。

由于结果很大,输出结果 mod m\bmod \space m 的值即可。

输入格式

第一行两个正整数 n,mn,m

第二行四个正整数 p,q,r,tp,q,r,t

第三行三个正整数 u,v,wu,v,w

第四行三个正整数 x,y,zx,y,z

输出格式

共三行,每行一个名字 + 一个空格 + 一个整数。
依次是 nodgd,Ciocio,Nicole 和他们在第 nn 天刷题数量 mod m\bmod \space m 的值。

4 10007
2 1 1 1
2 2 3
1 1 2
nodgd 74
Ciocio 80
Nicole 59

提示

对于 100%100\% 的数据,4n10164\le n \le 10^{16}2m10162\le m \le 10^{16}1p,q,r,t,u,v,w,x,y,z1001\le p,q,r,t,u,v,w,x,y,z \le 100