Language: C++

#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>
#include <string>
#include <iostream>
#include <stack>
#include <tuple>
#include <map>

using namespace std;
typedef long long ll;

long long MOD = 1000000007;
struct mint{
    long long v;

    mint() : v(0) {}
    mint(long long x){
        x = x % MOD;
        if(x < 0){ x += MOD; }
        v = x;
    }
    mint& operator+=(mint a){
        v += a.v;
        if(v >= MOD){ v -= MOD; }
        return *this;
    }
    mint& operator*=(mint a){
        v *= a.v;
        v %= MOD;
        return *this;
    }
    mint& operator-=(mint a){
        v -= a.v;
        if(v < 0){ v += MOD; }
        return *this;
    }
    mint& operator/=(mint a){
        return (*this) *= a.inv();
    }

    mint operator*(mint a) const {
        return mint(v) *= a;
    }

    mint operator+(mint a) const {
        return mint(v) += a;
    }

    mint operator-(mint a) const{
        return mint(v) -= a;
    }

    mint pow(long long k) const{
        mint res(1),tmp(v);
        while(k){
            if(k&1) res *= tmp;
            tmp *= tmp;
            k >>= 1;
        }
        return res;
    }
    mint inv() const {return pow(MOD - 2); }

    static mint comb(long long n, int k){
        mint res(1);
        for(int i = 0; i < k; ++i){
            res *= mint(n - i);
            res /= mint(i + 1);
        }
        return res;
    }

    static mint factorial(long long n){
        mint res(1);
        for(int i = n; i > 1; --i){
            res *= mint(i);
        }
        return res;
    }

    bool operator<(const mint &a) const {
        return v < a.v;
    };
};

template<class T>
struct Matrix {
    int nrow, ncol;
    vector<T> v;

    static Matrix<T> identity(int n){
        Matrix<T> ret(n, n);
        for(int i = 0; i < n; ++i){ ret.at(i, i) = 1; }
        return ret;
    }

    Matrix(int nrow, int ncol) : nrow(nrow), ncol(ncol), v(nrow * ncol, 0) {};
    Matrix(const Matrix<T>& m) : nrow(m.nrow), ncol(m.ncol), v(m.v) {};
    T& at(int i, int j){ return v.at(i * ncol + j); }
    const T& at(int i, int j) const { return v.at(i * ncol + j); }

    Matrix<T> operator*(const Matrix<T>& other){
        assert(ncol == other.nrow);
        Matrix<T> ret(nrow, other.ncol);
        for(int i = 0; i < nrow; ++i){
            for(int j = 0; j < other.ncol; ++j){
                for(int k = 0; k < ncol; ++k){
                    ret.at(i, j) += this->at(i, k) * other.at(k, j);
                }
            }
        }
        return ret;
    }

    vector<T> operator*(const vector<T>& v){
        assert(ncol == v.size());
        vector<T> ret(nrow, 0);
        for(int i = 0; i < nrow; ++i){
            for(int j = 0; j < ncol; ++j){
                ret.at(i) += this->at(i, j) * v.at(j);
            }
        }
        return ret;
    }

    Matrix<T> pow(long long k){
        assert(nrow == ncol);
        Matrix<T> ret(Matrix<T>::identity(nrow));
        Matrix<T> tmp(*this);
        while(k){
            if(k & 1) ret = ret * tmp;
            tmp = tmp * tmp;
            k >>= 1;
        }
        return ret;
    }
};

template<class T>
vector<T> operator*(const vector<T>& v, const Matrix<T>& m){
    assert(v.size() == m.nrow);
    vector<T> ret(m.ncol, 0);
    for(int i = 0; i < ret.size(); ++i){
        for(int j = 0; j < v.size(); ++j){
            ret.at(i) += v.at(j) * m.at(j, i);
        }
    }
    return ret;
}

Matrix<mint> calc_pow(int num_digits, ll pow, ll b){
    Matrix<mint> x(3, 3);
    x.at(0, 0) = mint(10).pow(num_digits);
    x.at(1, 0) = 1;
    x.at(1, 1) = 1;
    x.at(2, 1) = b;
    x.at(2, 2) = 1;
    return x.pow(pow);
}

int main(){
    ll l, a, b, m;
    cin >> l >> a >> b >> m;
    MOD = m;

    // d 桁の個数 nd を数える。
    vector<ll> nd(18, 0);
    for(ll i = 0; i < nd.size(); ++i){
        ll x = max((long long)((pow((long double)10, i + 1) - 1 - a) / b), 0LL) + 1;
        x = min(x, l);
        if(i == 0){
            nd.at(i) = x;
        }else{
            ll y = max((long long)((pow((long double)10, i) - 1 - a) / b), 0LL) + 1;
            y = min(y, l);
            nd.at(i) = x - y;
        }
    }

    // 各 i 桁に対して 行列の nd 乗を計算する
    vector<Matrix<mint>> tmp;
    for(ll i = 0; i < nd.size(); ++i){
        if(nd.at(i) == 0){
            tmp.push_back(Matrix<mint>(0, 0)); // dummy
        }else{
            tmp.push_back(calc_pow(i + 1, nd.at(i), b));
        }
    }

    // i = 1, 2, ... 18 に対して順にかけていく
    vector<mint> v(3, 0);
    v.at(0) = 0; v.at(1) = a; v.at(2) = 1;
    for(ll i = 0; i < nd.size(); ++i){
        if(nd.at(i) == 0){ continue; }
        v = v * tmp.at(i);
    }

    cout << v.at(0).v << endl;
    return 0;
}


Compiler output:
a.cc: In member function 'Matrix<T> Matrix<T>::operator*(const Matrix<T>&)':
a.cc:106:9: error: there are no arguments to 'assert' that depend on a template parameter, so a declaration of 'assert' must be available [-fpermissive]
  106 |         assert(ncol == other.nrow);
      |         ^~~~~~
a.cc:106:9: note: (if you use '-fpermissive', G++ will accept your code, but allowing the use of an undeclared name is deprecated)
a.cc: In member function 'Matrix<T> Matrix<T>::pow(long long int)':
a.cc:130:9: error: there are no arguments to 'assert' that depend on a template parameter, so a declaration of 'assert' must be available [-fpermissive]
  130 |         assert(nrow == ncol);
      |         ^~~~~~
a.cc: In instantiation of 'Matrix<T> Matrix<T>::pow(long long int) [with T = mint]':
a.cc:161:17:   required from here
  161 |     return x.pow(pow);
      |            ~~~~~^~~~~
a.cc:130:15: error: 'assert' was not declared in this scope
  130 |         assert(nrow == ncol);
      |         ~~~~~~^~~~~~~~~~~~~~
a.cc:11:1: note: 'assert' is defined in header '<cassert>'; this is probably fixable by adding '#include <cassert>'
   10 | #include <map>
  +++ |+#include <cassert>
   11 | 
a.cc: In instantiation of 'std::vector<T> operator*(const std::vector<T>&, const Matrix<T>&) [with T = mint]':
a.cc:198:25:   required from here
  198 |         v = v * tmp.at(i);
      |                         ^
a.cc:144:11: error: 'assert' was not declared in this scope
  144 |     assert(v.size() == m.nrow);
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~
a.cc:144:11: note: 'assert' is defined in header '<cassert>'; this is probably fixable by adding '#include <cassert>'