RxExCxCx

#include <fstream>
#include <cstring>
#include <algorithm>
#define LL long long
#define MAX 1000001
using namespace std;
struct matrice
{
    int M[4][4];
};
matrice C;
LL N;
int B,X,K,I,A[4],vs[MAX],vd[MAX];

matrice inmultire(matrice A,matrice B) /// C=A*B
{
    matrice C;
    memset(C.M,0,sizeof(C.M));
    for(int i=0;i<4;++i)
        for(int j=0;j<4;++j)
            for(int k=0;k<4;++k)
                C.M[i][j]=(C.M[i][j]+1LL*A.M[i][k]*B.M[k][j])%K;
    return C;
}

matrice putere(matrice A,LL N) /// P=A^N (logadrtmic)
{
    if(N==1)
        return A;
    if(N%2==1)
        return inmultire(A,putere(A,N-1));
    matrice P=putere(A,N/2);
    return inmultire(P,P);
}

LL sol;

int F(int val) /// Cautare binara (cauta pe v in vectorul v)
{
    for(int st=1,dr=I;st<=dr;)
    {
        int mij=(st+dr)/2;
        if(vs[mij]==val)
            return vd[mij];
        if(vs[mij]<val)
            st=mij+1;
        else
            dr=mij-1;
    }
    return 0;
}

int main()
{
    ifstream f("recc.in");
    f>>N>>B>>X>>K;
    for(int i=0;i<4;++i)
        f>>A[i],C.M[3-i][3]=A[i]%K;
    f.close();
    for(int i=0;i<3;++i)
        C.M[i+1][i]=1;
    C=putere(C,N-4);
    for(int i=0;i<4;++i)
        A[i]=C.M[i][3];
    for(int i=1;i<=B;++i)
        for(int j=1;j<=B;++j)
            vs[++I]=(1LL*A[0]*i%K +1LL*A[1]*j%K)%K;
    sort(vs+1,vs+I+1);
    int II=1;
    vd[1]=1;
    for(int i=2;i<=I;++i)
        if(vs[II]!=vs[i])
            vs[++II]=vs[i],vd[II]=1;
        else
            ++vd[II];
    I=II;
    LL sol=0;
    for(int i=1;i<=B;++i)
        for(int j=1;j<=B;++j)
        {
            int v=(1LL*A[2]*i%K+1LL*A[3]*j%K)%K;
            v=(X-v+K)%K;
            sol+=F(v);
        }
    ofstream g("recc.out");
    g<<sol<<'\n';
    g.close();
    return 0;
}