f9gE8q - Online C++ Compiler & Debugging Tool

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll add(ll a,ll b,ll MOD) {
    a%=MOD;b%=MOD;a += b;
    if (a >= MOD) a -= MOD;
    return a;
}
inline ll sub(ll a,ll b,ll MOD) {
    a%=MOD;b%=MOD;a -= b;
    if (a < 0) a += MOD;
    return a;
}
inline ll mul(ll a,ll b,ll MOD) {
    return a * b % MOD;
}
struct Mat{
    int r,c;
    vector<vector<ll>> mat;
    Mat(int r , int c): r(r) , c(c), mat(r, vector<ll>(c,0)) {}
};
Mat mul_mat(Mat &m1,Mat &m2,ll MOD) {
    Mat res(m1.r, m2.c);
    for(int i=0;i<res.r;i++) for(int j=0;j<res.c;j++) {
        ll sum=0;
        for(int k=0;k<m1.c;k++) {
            sum+= m1.mat[i][k] * m2.mat[k][j]%MOD;
            if(sum>=MOD) sum-=MOD;
        }
        res.mat[i][j]=sum;
    }
    return res;
}
Mat I(int n){
    Mat res(n,n);
    for(int i=0;i<n;i++) res.mat[i][i] = 1;
    return res;
}
Mat bin_exp(Mat a , ll b,ll MOD) {
    Mat res = I(a.r);
    while (b) {
        if (b & 1) res =mul_mat(res,a,MOD);
        a =mul_mat(a,a,MOD);
        b >>= 1;
    }
    return res;
}
vector<ll> mul_mat_vec(const Mat A, const vector<ll> v,ll MOD) {
    int M = A.r;
    vector<ll> r(M);
    for (int i = 0; i < M; i++) {
        ll sum = 0;
        for (int j = 0; j < M; j++){
               sum+=A.mat[i][j]*v[j]%MOD;
               if(sum>=MOD)sum-=MOD;
        }
        r[i] = sum;
    }
    return r;
}
int main() {
	string x;ll k,m;cin>>x>>k>>m;
	ll rem=0;
	for(auto ch:x){
		rem*=10;
		rem+=ch-'0';rem%=m;
	}
	ll pow10=1;
    for(int i=0;i<x.size();i++) pow10=(pow10*10)%m;
    Mat trans(2,2);
    trans.mat[0][0]=pow10;trans.mat[0][1]=rem;
    trans.mat[1][0]=0;trans.mat[1][1]=1;
    Mat T=bin_exp(trans,k,m);
    vector<ll>base={0,1};
    base=mul_mat_vec(T,base,m);
    if(base[0]%m==0)cout<<"YES\n";
    else cout<<"NO\n";
	return 0;
}