按照题目提示，构造矩阵，用矩阵快速幂求解

构造矩阵：

大家一定做过这种题：求斐波那契数列第 N 项%1e9+7(N<=1e18)
单纯从数学上讲，我们可以使用矩阵快速幂解决。由于斐波那契数列的递推公式非常简单，所以可以很方便的构造矩阵。
$f[i]=f[i-1]+f[i-2]$
$$
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix} \times
\begin{bmatrix}
f[i-1] \\
f[i-2]
\end{bmatrix} =
\begin{bmatrix}
f[i] \\
f[i-1]
\end{bmatrix}
$$

但是这个方程的参数是 “恒定” 的，也就是说，每一个 f[i] 都可以用 f[i-1] 和 f[i-2] 的 “恒定” 的 “线性” 组合得出（即单纯的相加）。
因此可以想象，$f[i]=a\times f[i-1]+b\times f[ i-2 ] (a,b 为定值)$这样的方程的转移矩阵也非常简单。
考虑更加特殊的方程:$f[i]=i^2$
显然这个是可以用矩阵快速幂优化为 O(logn) 求的 (因为你完全可以 O(1) 求，我们让它 O(logn) 求它若不肯岂不太不给面子了)
具体的转移矩阵是：
$$
\begin{bmatrix}
(i-1)^2\\
(i-1)\\
1
\end{bmatrix} \times
\begin{bmatrix}
1 & 0 & 1\\
2 & 1 & 1\\
0 & 0 & 1
\end{bmatrix} =
\begin{bmatrix}
i^2\\
i\\
1
\end{bmatrix}
$$
这样，我们就可以很容易地写出这道题的转移矩阵：
$$
\begin{bmatrix}
\begin{smallmatrix}
p & 1 & 1 & q & 0 & 0 & 0 & 0 & t & 0 & r & 1\\
1 & u & 1 & 0 & v & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & x & 0 & 0 & y & 0 & 1 & 0 & 1 & 0 & 0\\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & w & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & z & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 1 & -3\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1
\end{smallmatrix}
\end{bmatrix}\times
\begin{bmatrix}
\begin{smallmatrix}
a[i-1]\\
b[i-1]\\
c[i-1]\\
a[i-2]\\
b[i-2]\\
c[i-2]\\
w^{i-2}\\
z^{i-2}\\
i-2\\
i\\
(i-2)^2\\
1
\end{smallmatrix}
\end{bmatrix}=
\begin{bmatrix}
\begin{smallmatrix}
a[i]\\
b[i]\\
c[i]\\
a[i-1]\\
b[i-1]\\
c[i-1]\\
w^{i-1}\\
z^{i-1}\\
i-1\\
i+1\\
(i-1)^2\\
1
\end{smallmatrix}
\end{bmatrix}
$$
但是注意一点，能用矩阵快速幂优化的转移矩阵，必须是如上的参数为恒值的。
比如 $f[x]=f[x-1]+x\times f[x-2]$貌似就不能用矩阵快速幂优化 (至少我不会)

代码实现：

注意到乘法时会出现超出 long long 范围的情况，因此我们可以使用一种黑科技：O(1) 快速乘
将 long long 强制转化为 double，在误差的情况下进行乘法即可。

这样，总的时间复杂度依旧是 o(nlogn)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define reg register

using namespace std;

typedef long long ll;
typedef struct mat_t
{
    ll x[13][13];
    void out()
    {
        for(int i=1;i<=12;i++)
        {
            for(int j=1;j<=12;j++)cout<<x[i][j]<<" ";
            cout<<endl;
        }
    }
}mat;

ll mod,n;
ll p,q,r,t,u,v,w,x,y,z;
inline ll mul(ll a,ll b)//O(1) 快速乘
{
    ll d=(ll)floor(a*(double)b/mod+0.5);
    ll ret=a*b-d*mod;
    if(ret<0)ret+=mod;
    return ret;
}

mat mul_mat(mat a,mat b)
{
    ll t;
    mat c;
    memset(c.x,0,sizeof(c.x));
    for(int i=1;i<=12;i++)
        for(int j=1;j<=12;j++)
        {
            for(int k=1;k<=12;k++)
                c.x[i][j]+=mul(a.x[i][k],b.x[k][j]);
            c.x[i][j]>mod?c.x[i][j]%=mod:1;
        }
    return c;
}

mat ksm_mat(mat a,ll t)
{
    mat ans,now=a;
    memset(ans.x,0,sizeof(ans.x));
    for(int i=1;i<=12;i++)ans.x[i][i]=1;
    while(t)
    {
        if(t&1LL)ans=mul_mat(ans,now);
        now=mul_mat(now,now);
        t>>=1LL;
    }
    return ans;
}

void work()
{
    mat a,b,ans;
    memset(a.x,0,sizeof(a.x));
    memset(b.x,0,sizeof(b.x));
    a.x[1][1]=p,a.x[1][2]=a.x[1][3]=1,a.x[1][4]=q,a.x[1][9]=t,a.x[1][11]=r,a.x[1][12]=1;
    a.x[2][1]=1,a.x[2][2]=u,a.x[2][3]=1,a.x[2][5]=v,a.x[2][7]=1;
    a.x[3][1]=a.x[3][2]=1,a.x[3][3]=x,a.x[3][6]=y,a.x[3][8]=1,a.x[3][10]=1;
    a.x[4][1]=1;
    a.x[5][2]=1;
    a.x[6][3]=1;
    a.x[7][7]=w;
    a.x[8][8]=z;
    a.x[9][9]=1,a.x[9][12]=1;
    a.x[10][10]=1,a.x[10][12]=1;
    a.x[11][10]=2,a.x[11][11]=1,a.x[11][12]=mod-3;
    a.x[12][12]=1;
    b.x[1][1]=b.x[2][1]=b.x[3][1]=3;
    b.x[4][1]=b.x[5][1]=b.x[6][1]=1;
    b.x[7][1]=w;
    b.x[8][1]=z;
    b.x[9][1]=1;
    b.x[10][1]=3;
    b.x[11][1]=b.x[12][1]=1;
    a=ksm_mat(a,n-2);
    ans=mul_mat(a,b);
    printf("nodgd %lld\nCiocio %lld\nNicole %lld\n",ans.x[1][1],ans.x[2][1],ans.x[3][1]);
}

void input()
{
    scanf("%lld%lld",&n,&mod);
    scanf("%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld",&p,&q,&r,&t,&u,&v,&w,&x,&y,&z);
}

int main()
{
    input();
    work();
    return 0;
}