You are given <var>Q</var> tuples of integers <var>(L_i, A_i, B_i, M_i)</var>. For each tuple, answer the following question. 
There is an arithmetic progression with L terms: s_0, s_1, s_2, ... , s_{L-1}.
The initial term is A, and the common difference is B. That is, s_i = A + B \times i holds.
Consider the integer obtained by concatenating the terms written in base ten without leading zeros. For example, the sequence 3, 7, 11, 15, 19 would be concatenated into 37111519. What is the remainder when that integer is divided by M?

-----Constraints-----
 - All values in input are integers.
 - 1 \leq L, A, B < 10^{18}
 - 2 \leq M \leq 10^9
 - All terms in the arithmetic progression are less than 10^{18}.

-----Input-----
Input is given from Standard Input in the following format:
L A B M

-----Output-----
Print the remainder when the integer obtained by concatenating the terms is divided by M.

-----Sample Input-----
5 3 4 10007

-----Sample Output-----
5563

Our arithmetic progression is 3, 7, 11, 15, 19, so the answer is 37111519 mod 10007, that is, 5563.

Difficulty: interview

Starter code:

Solutions:
import copy
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

L,A,B,mod = na()

low = 1
high = 10


def matpow(M, v, e, mod):
    A = copy.deepcopy(M)
    w = copy.deepcopy(v)
    while e > 0:
        if e&1:
            w = mulv(A, w, mod)
        A = mul(A, A, mod)
        e >>= 1
    return w


def mulv(M, v, mod):
    n = len(M)
    m = len(v)
    ret = [0] * n
    for i in range(n):
        s = 0
        for j in range(m):
            s += M[i][j] * v[j]
        ret[i] = s % mod
    return ret


def mul(A, B, mod):
    n = len(A)
    m = len(B)
    o = len(B[0])
    ret = [[0] * o for _ in range(n)]
    for i in range(n):
        for j in range(o):
            s = 0
            for k in range(m):
                s += A[i][k] * B[k][j]
            ret[i][j] = s % mod
    return ret


# x = x * high + val
# val += B
# (high 1 0)
# (0 1 1)
# (0 0 1)

v = [0, A, B]
ra = A

while low < 1e18:
    mat = [[high%mod, 1, 0], [0, 1, 1], [0, 0, 1]]
    step = max(0, min(L, (high-ra+B-1)//B))
    v = matpow(mat, v, step, mod)
    # print(low, high, step, ra + B*step, v)
    ra = ra + B * step
    L -= step

    low *= 10
    high *= 10

print((v[0]))


l, a, b, m = [int(i) for i in input().split()]

cd = []
for i in range(18):
    cd.append(max(0, (10 ** (i + 1) - 1 - a) // b + 1))
    if cd[-1] >= l:
        cd[-1] = l
        break

cd_sum = 0
cd_2 = []

for i in cd:
    cd_2.append(i-cd_sum)
    cd_sum += i-cd_sum

X = [0, a, 1]
B = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
for i in range(len(cd_2)):
    A = [[(10 ** (i + 1)), 0, 0], [1, 1, 0], [0, b, 1]]
    B = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]

    n = cd_2[i]
    while n > 0:
        if n % 2 == 1:
            B = [[(B[0][0] * A[0][0] + B[0][1] * A[1][0] + B[0][2] * A[2][0]) % m,
                  (B[0][0] * A[0][1] + B[0][1] * A[1][1] + B[0][2] * A[2][1]) % m,
                  (B[0][0] * A[0][2] + B[0][1] * A[1][2] + B[0][2] * A[2][2]) % m],
                 [(B[1][0] * A[0][0] + B[1][1] * A[1][0] + B[1][2] * A[2][0]) % m,
                  (B[1][0] * A[0][1] + B[1][1] * A[1][1] + B[1][2] * A[2][1]) % m,
                  (B[1][0] * A[0][2] + B[1][1] * A[1][2] + B[1][2] * A[2][2]) % m],
                  [(B[2][0] * A[0][0] + B[2][1] * A[1][0] + B[2][2] * A[2][0]) % m,
                   (B[2][0] * A[0][1] + B[2][1] * A[1][1] + B[2][2] * A[2][1]) % m,
                   (B[2][0] * A[0][2] + B[2][1] * A[1][2] + B[2][2] * A[2][2]) % m]]

            n -= 1

        else:
            A = [[(A[0][0] * A[0][0] + A[0][1] * A[1][0] + A[0][2] * A[2][0]) % m,
                  (A[0][0] * A[0][1] + A[0][1] * A[1][1] + A[0][2] * A[2][1]) % m,
                  (A[0][0] * A[0][2] + A[0][1] * A[1][2] + A[0][2] * A[2][2]) % m],
                 [(A[1][0] * A[0][0] + A[1][1] * A[1][0] + A[1][2] * A[2][0]) % m,
                  (A[1][0] * A[0][1] + A[1][1] * A[1][1] + A[1][2] * A[2][1]) % m,
                  (A[1][0] * A[0][2] + A[1][1] * A[1][2] + A[1][2] * A[2][2]) % m],
                  [(A[2][0] * A[0][0] + A[2][1] * A[1][0] + A[2][2] * A[2][0]) % m,
                   (A[2][0] * A[0][1] + A[2][1] * A[1][1] + A[2][2] * A[2][1]) % m,
                   (A[2][0] * A[0][2] + A[2][1] * A[1][2] + A[2][2] * A[2][2]) % m]]
            n //= 2

    X[0] = (X[0] * B[0][0] + X[1] * B[1][0] + X[2] * B[2][0]) % m
    X[1] = (X[0] * B[0][1] + X[1] * B[1][1] + X[2] * B[2][1]) % m
    X[2] = (X[0] * B[0][2] + X[1] * B[1][2] + X[2] * B[2][2]) % m

print((X[0] % m))


import sys


def dot(A, B, mod):
    r = len(A)
    c = len(B[0])
    m = len(A[0])
    res = [[0] * c for _ in range(r)]
    for i in range(r):
        for j in range(c):
            for k in range(m):
                res[i][j] += A[i][k] * B[k][j] % mod
                res[i][j] %= mod
    return res


def rec_pow(k, n, mod):
    if n == 1:
        return k

    k2 = dot(k, k, mod)
    if n % 2 == 0:
        return rec_pow(k2, n//2, mod)
    else:
        return dot(rec_pow(k2, n//2, mod), k, mod)


def main():
    input = sys.stdin.readline
    L, A, B, M = list(map(int, input().split()))

    s = [[0, A%M, 1]]
    for d in range(1, 19):
        n1 = min(max(0, (10**d - 1 - A) // B + 1), L)
        n0 = min(max(0, (10**(d-1) - 1 - A) // B + 1), L)
        n = n1 - n0
        if n == 0:
            continue

        k = [[pow(10, d, M), 0, 0],\
             [1, 1, 0],\
             [0, B%M, 1]]
        s = dot(s, rec_pow(k, n, M), M)

        if n1 >= L:
            break

    return s[0][0]

def __starting_point():
    print((main()))

__starting_point()

def mat_dot(one, two, mod):
	return [[sum([(one[i][k]*two[k][j])%mod for k in range(len(two))])%mod for j in range(len(two[0]))] for i in range(len(one))]

def mat_pow(mat, exp, mod):
	size = len(mat)
	res = [[0 for _ in range(size)] for _ in range(size)]
	for i in range(size):
		res[i][i] = 1
	cnt = 0
	while (1<<cnt) <= exp:
		if (exp>>cnt)&1:
			res = mat_dot(res, mat, mod)
		mat = mat_dot(mat, mat, mod)
		cnt += 1
	return res

l, a, b, m = map(int, input().split())
c = a + (l-1)*b
n = len(str(c))
dgt = [0 for _ in range(n+1)]
for i in range(1, n):
	dgt[i] = max(0, (10**i -a+b-1) // b) - max(0, (10**(i-1) -a+b-1) // b)
dgt[n] = l-sum(dgt)
d_sum = [0 for _ in range(n+1)]
for i in range(n-1, 0, -1):
	d_sum[i] = d_sum[i+1] + dgt[i+1]*(i+1)
fr = [0 for _ in range(n+1)]
fr[1] = a
for i in range(2, n+1):
	fr[i] = fr[i-1] + b*dgt[i-1]
l = [[0, a%m, 1]]
for d in range(1, n+1):
	k = [[(10**d)%m, 0, 0], [1, 1, 0], [0, b%m, 1]]
	j = mat_pow(k, dgt[d], m)
	l = mat_dot(l, j, m)

print(l[0][0]%m)

def f_takahashi_basics_in_education_and_learning(L, A, B, M, DIGIT_MAX=18):
    import numpy

    # https://github.com/numpy/numpy/blob/master/numpy/linalg/linalg.py L560から
    def matrix_power(a, n):
        a = numpy.core.asanyarray(a)
        fmatmul = numpy.core.dot

        z = result = None
        while n > 0:
            z = a % M if z is None else fmatmul(z, z) % M
            n, bit = divmod(n, 2)
            if bit:
                result = z if result is None else fmatmul(result, z) % M
        return result

    # 数列に対して、d桁の要素の個数を求める
    num_pow_d = [0] * (DIGIT_MAX + 1)
    for d in range(DIGIT_MAX + 1):
        if 10**d - 1 >= A:
            # dに対してA + B*n <= 10**d - 1 となる最大のn(L以下しか取りえない)
            num_pow_d[d] = min(((10**d - 1 - A) // B) + 1, L)  # +1はnが0スタートのため

    ans = numpy.array([0, A, 1])
    for d in range(1, DIGIT_MAX + 1):
        c_d = num_pow_d[d] - num_pow_d[d - 1]
        matrix = numpy.array([[(10**d) % M, 0, 0], [1, 1, 0], [0, B, 1]], dtype='object')
        m = numpy.eye(3, dtype='object') if c_d == 0 else matrix_power(matrix, c_d)
        ans = ans.dot(m) % M
    return ans[0]

L, A, B, M = [int(i) for i in input().split()]
print(f_takahashi_basics_in_education_and_learning(L, A, B, M))

import sys
import itertools
import queue
input = sys.stdin.readline
sys.setrecursionlimit(100000)
# mod = 10 ** 9 + 7

def read_values(): return list(map(int, input().split()))
def read_index(): return [int(x) - 1 for x in input().split()]
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n) 


def mat_mul(X, Y, mod):
    m = len(X)
    return [[sum(X[i][k] * Y[k][j] % mod for k in range(m)) % mod for j in range(m)] for i in range(m)]


def mat_pow(M, k, mod):
    m = len(M)
    res = [[1 if i == j else 0 for j in range(m)] for i in range(m)]
    while k > 0:
        if k & 1:
            res = mat_mul(M, res, mod)
        M = mat_mul(M, M, mod)
        k >>= 1

    return res


def main():
    L, A, B, M = read_values()
    res = 0
    D = [(0, 0)]
    for d in range(1, 20):
        l = D[-1][1]
        r = max(0, min((10 ** d - 1 - A) // B + 1, L))
        D.append((l, r))
    
    res = 0
    c = 0
    R = [0, A, 1]
    Mat = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
    for d in range(1, 20):
        num = D[d][1] - D[d][0]

        MM = [[10 ** d, 0, 0], [1, 1, 0], [0, B, 1]]
        Mat = mat_mul(Mat, mat_pow(MM, num, M), M)

    X = sum(R[i] * Mat[i][0] % M for i in range(3)) % M

    print(X)


def __starting_point():
    main()

__starting_point()

l,a,b,m = map(int,input().split())

# c111 -> 1001001001みたいなやつを求める
# n : 塊の数
# l : 一つの塊(00..001)の長さ
# m : mod
# ex) n=3, l=2 -> 10101
def c111(n, l, m):
    if n <= 1:
        return 1
    if n % 2 == 1:
        return (c111(n - 1, l, m) * pow(10, l, m) + 1) % m
    half = c111(n // 2, l, m)
    return (half * pow(10, (n // 2) * l, m) + half) % m

# c123 -> 1002003004みたいなやつを求める
# n : 塊の数
# l : 一つの塊(00..001)の長さ
# m : mod
# ex) n=3, l=2 -> 10203
def c123(n, l, m):
    if n <= 1:
        return 1
    if n % 2 == 1:
        return (c123(n - 1, l, m) + c111(n, l, m)) % m
    half = c123(n // 2, l, m)
    return (half * pow(10, (n // 2) * l, m) + half + (n // 2) * c111(n // 2, l, m)) % m

fst = a
lst = a + b * (l - 1)

fst_l = len(str(fst))
lst_l = len(str(lst))

res = 0
margin = 0
for keta in reversed(range(fst_l, lst_l + 1)):
    num_l = a + b * ((10 ** (keta - 1) - a + b - 1) // b)
    num_r = a + b * ((10 ** keta - a + b - 1) // b - 1)
    if keta == fst_l:
        num_l = fst
    if keta == lst_l:
        num_r = lst
    if num_l > num_r:
        continue
    sz = (num_r - num_l) // b + 1
    _111 = num_l * c111(sz, keta, m)
    _123 = b * c123(sz - 1, keta, m)
    if sz == 1:
        _123 = 0
    res += (pow(10, margin, m) * (_111 + _123)) % m
    margin += sz * keta
print(res % m)

L, a, b, m = map(int, input().split())
ans = 0
for k in range(1, 37):
  l = (10**(k-1)-a+b-1)//b
  r = (10**k-a+b-1)//b
  l = max(l, 0)
  r = min(r, L)
  if l >= r:
    continue
  d = r - l
  c = a+b*(r-1)
  t = 10**k-1
  x = b*pow(10, k, m*t*t)*(pow(10, k*(d-1), m*t*t)-1)
  x %= m*t*t
  x //= t
  y = (c-(d-1)*b)*pow(10, d*k, m*t)
  y %= m*t
  s = x+y-c
  s %= m*t
  s //= t
  ans *= pow(10, d*k, m)
  ans += s
  ans %= m
print(ans)

def solve(L, A, B, M):
    ret, digits = 0, 0
    for d in range(18, 0, -1):
        lo = 10 ** (d - 1)
        hi = 10 ** d - 1
        if hi < A or A + B * (L - 1) < lo:
            continue
        imin = 0 if lo <= A else (lo - A + B - 1) // B
        init = A + B * imin
        if init > hi:
            continue
        imax = L - 1 if A + B * (L - 1) <= hi else imin + (hi - init) // B
        n = imax - imin + 1
        p = 10 ** d % M
        a = matpow([[1, 0, 1, 0], [0, 1, 0, 1], [0, 0, p, p], [0, 0, 0, p]], n, M)
        # a[0][3] = sum p^i for i in [0, n-1]
        # a[1][3] = sum i * p^i for i in [0, n-1]
        # sum (A + B * (imax - i)) * p^i for i in [0, n-1]
        sub = (A + B * imax) % M * a[1][3] % M + M - (B * a[0][3] % M)
        ret += sub % M * pow10(digits, M) % M
        digits += d * (imax - imin + 1)
    return ret % M


def pow10(p, mod):
    if p % 2 == 1:
        return 10 * pow10(p - 1, mod) % mod
    elif p > 0:
        sub = pow10(p // 2, mod)
        return sub * sub % mod
    else:
        return 1


def matpow(a, p, mod):
    if p % 2 == 1:
        return matmul(a, matpow(a, p - 1, mod), mod)
    elif p > 0:
        b = matpow(a, p // 2, mod)
        return matmul(b, b, mod)
    else:
        n = len(a)
        return [[1 if i == j else 0 for j in range(n)] for i in range(n)]


def matmul(a, b, mod):
    n = len(a)
    ret = [[0 for j in range(n)] for i in range(n)]
    for i in range(n):
        for k in range(n):
            for j in range(n):
                ret[i][j] += a[i][k] * b[k][j]
        for j in range(n):
            ret[i][j] %= mod
    return ret


L, A, B, M = list(map(int, input().split()))
print((solve(L, A, B, M)))


class SquareMatrix():
    def __init__(self, n, mod=1000000007):
        self.n = n
        self.mat = [[0 for j in range(n)] for i in range(n)]
        self.mod = mod

    @staticmethod
    def id(n, mod=1000000007):
        res = SquareMatrix(n, mod)
        for i in range(n):
            res.mat[i][i] = 1
        return res

    @staticmethod
    def modinv(n, mod):
        assert n % mod != 0
        c0, c1 = n, mod
        a0, a1 = 1, 0
        b0, b1 = 0, 1
        while c1:
            a0, a1 = a1, a0 - c0 // c1 * a1
            b0, b1 = b1, b0 - c0 // c1 * b1
            c0, c1 = c1, c0 % c1
        return a0 % mod

    def set(self, arr):
        for i in range(self.n):
            for j in range(self.n):
                self.mat[i][j] = arr[i][j] % self.mod

    def operate(self, vec):
        assert len(vec) == self.n
        res = [0 for _ in range(self.n)]
        for i in range(self.n):
            for j in range(self.n):
                res[i] += self.mat[i][j] * vec[j]
                res[i] %= self.mod
        return res

    def add(self, other):
        assert other.n == self.n
        res = SquareMatrix(self.n, self.mod)
        for i in range(self.n):
            for j in range(self.n):
                res.mat[i][j] = self.mat[i][j] + other.mat[i][j]
                res.mat[i][j] %= self.mod
        return res

    def subtract(self, other):
        assert other.n == self.n
        res = SquareMatrix(self.n, self.mod)
        for i in range(self.n):
            for j in range(self.n):
                res.mat[i][j] = self.mat[i][j] - other.mat[i][j]
                res.mat[i][j] %= self.mod
        return res

    def times(self, k):
        res = SquareMatrix(self.n, self.mod)
        for i in range(self.n):
            for j in range(self.n):
                res.mat[i][j] = self.mat[i][j] * k
                res.mat[i][j] %= self.mod
        return res

    def multiply(self, other):
        assert self.n == other.n
        res = SquareMatrix(self.n, self.mod)
        for i in range(self.n):
            for j in range(self.n):
                for k in range(self.n):
                    res.mat[i][j] += self.mat[i][k] * other.mat[k][j]
                    res.mat[i][j] %= self.mod
        return res

    def power(self, k):
        tmp = SquareMatrix(self.n, self.mod)
        for i in range(self.n):
            for j in range(self.n):
                tmp.mat[i][j] = self.mat[i][j]
        res = SquareMatrix.id(self.n, self.mod)
        while k:
            if k & 1:
                res = res.multiply(tmp)
            tmp = tmp.multiply(tmp)
            k >>= 1
        return res

    def trace(self):
        res = 0
        for i in range(self.n):
            res += self.mat[i][i]
            res %= self.mod
        return res

    def determinant(self):
        res = 1
        tmp = SquareMatrix(self.n, self.mod)
        for i in range(self.n):
            for j in range(self.n):
                tmp.mat[i][j] = self.mat[i][j]
        for j in range(self.n):
            if tmp.mat[j][j] == 0:
                for i in range(j + 1, self.n):
                    if tmp.mat[i][j] != 0:
                        idx = i
                        break
                else:
                    return 0
                for k in range(self.n):
                    tmp.mat[j][k], tmp.mat[idx][k] = tmp.mat[idx][k], tmp.mat[j][k]
                res *= -1
            inv = SquareMatrix.modinv(tmp.mat[j][j], self.mod)
            for i in range(j + 1, self.n):
                c = -inv * tmp.mat[i][j] % self.mod
                for k in range(self.n):
                    tmp.mat[i][k] += c * tmp.mat[j][k]
                    tmp.mat[i][k] %= self.mod
        for i in range(self.n):
            res *= tmp.mat[i][i]
            res %= self.mod
        return res

    def transpose(self):
        res = SquareMatrix(self.n, self.mod)
        for i in range(self.n):
            for j in range(self.n):
                res.mat[i][j] = self.mat[j][i]
        return res

    def inverse(self): #self.determinant() != 0
        res = SquareMatrix.id(self.n, self.mod)
        tmp = SquareMatrix(self.n, self.mod)
        sgn = 1
        for i in range(self.n):
            for j in range(self.n):
                tmp.mat[i][j] = self.mat[i][j]
        for j in range(self.n):
            if tmp.mat[j][j] == 0:
                for i in range(j + 1, self.n):
                    if tmp.mat[i][j] != 0:
                        idx = i
                        break
                else:
                    return 0
                for k in range(self.n):
                    tmp.mat[j][k], tmp.mat[idx][k] = tmp.mat[idx][k], tmp.mat[j][k]
                    res.mat[j][k], res.mat[idx][k] = res.mat[idx][k], res.mat[j][k]
            inv = SquareMatrix.modinv(tmp.mat[j][j], self.mod)
            for k in range(self.n):
                tmp.mat[j][k] *= inv
                tmp.mat[j][k] %= self.mod
                res.mat[j][k] *= inv
                res.mat[j][k] %= self.mod
            for i in range(self.n):
                c = tmp.mat[i][j]
                for k in range(self.n):
                    if i == j:
                        continue
                    tmp.mat[i][k] -= tmp.mat[j][k] * c
                    tmp.mat[i][k] %= self.mod
                    res.mat[i][k] -= res.mat[j][k] * c
                    res.mat[i][k] %= self.mod
        return res

    def linear_equations(self, vec):
        return self.inverse().operate(vec)

L, A, B, M = map(int, input().split())

D = [0 for _ in range(18)]

for i in range(18):
    D[i] = (int('9' * (i + 1)) - A) // B + 1
    D[i] = max(D[i], 0)
    D[i] = min(D[i], L)

for i in range(17)[::-1]:
    D[i + 1] -= D[i]

mat = SquareMatrix.id(3, M)

for i in range(18):
    op = SquareMatrix(3, M)
    op.mat[0][0] = 10**(i + 1)
    op.mat[0][1] = 1
    op.mat[1][1] = 1
    op.mat[1][2] = B
    op.mat[2][2] = 1
    mat = op.power(D[i]).multiply(mat)

print(mat.operate([0, A, 1])[0])

import math
import numpy as np
from decimal import *
L,A,B,M=map(int, input().split())

def matpow(X,n,mod):
  E = np.eye(N=X.shape[0],dtype=int)
  Y = X%mod
  if n == 1:
    return Y
  else:
    return np.dot(matpow(np.dot(Y,Y)%mod,n//2,mod), (Y if n % 2 else E))%mod
  
a = 0
for d in range(1,19):
  left = math.ceil(Decimal(10**(d-1)-A)/Decimal(B))
  right = math.ceil(Decimal(10**d-A)/Decimal(B))-1
  if right < 0:
    continue
  if left > L-1:
    break
  if left > right:
    continue
  if left < 0:
    left = 0
  if right > L-1:
    right = L-1
  mat = np.matrix([[10**d,0,0],[1,1,0],[0,1,1]])
  result = np.dot(np.array([a,A+B*left,B])%M, matpow(mat,right-left+1,M))
  a = result[0,0]%M
  
print(a)

import numpy as np

L, A, B, M = map(int, input().split())

def dot(A, B, mod):
    r = len(A)
    c = len(B[0])
    m = len(A[0])
    res = [[0] * c for _ in range(r)]
    
    for i in range(r):
        for j in range(c):
            for k in range(m):
                res[i][j] += A[i][k] * B[k][j] % mod
                res[i][j] %= mod
    
    return res

def rec_pow(k, n, mod):
    if n == 1:
        return k
    
    k2 = dot(k, k, mod)
    if n % 2 ==0:
        return rec_pow(k2, n//2, mod)
    else:
        return dot(rec_pow(k2, n//2, mod), k, mod)

s = [[0, A%M, 1]]

for d in range(1, 19):
    n1 = min(max(0, (10**d-1-A)//B+1), L)
    n0 = min(max(0, (10**(d-1)-1-A)//B+1), L)
    n = n1 - n0
    if n == 0:
        continue
        
    k = [[pow(10, d, M), 0, 0], [1, 1, 0], [0, B%M, 1]]
    
    s = dot(s, rec_pow(k, n, M), M)
    
    if n1 >= L:
        break
        
print(s[0][0])

class Matrix:

  def __init__(self, mat, mod=10**9+7):
    assert(len(mat) and len(mat[0]))
    from copy import deepcopy
    self.MOD = mod
    self.mat = deepcopy(mat)

  def matunit(self, n):
    return Matrix([[(x==y) for x in range(n)] for y in range(n)], mod=self.MOD)

  def __add__(self, other):
    assert(len(self.mat)==len(other.mat) and len(self.mat[0])==len(other.mat[0]))
    h = len(self.mat)
    w = len(self.mat[0])
    ret = [[(self.mat[y][x]+other.mat[y][x])%self.MOD for x in range(w)] for y in range(h)]
    return ret

  def __mul__(self, other):
    assert(len(self.mat[0])==len(other.mat))
    h = len(self.mat)
    w = len(other.mat[0])
    ret = [[0 for _ in range(w)] for _ in range(h)]
    for y in range(h):
      for z in range(len(other.mat)):
        for x in range(w):
          ret[y][x] += self.mat[y][z]*other.mat[z][x]
    for y in range(h):
      for x in range(w):
        ret[y][x] %= self.MOD
    return Matrix(ret, mod=self.MOD)

  def __pow__(self, k):
    assert(len(self.mat)==len(self.mat[0]))
    from copy import deepcopy
    ret = self.matunit(len(self.mat))
    n = Matrix(deepcopy(self.mat), mod=self.MOD)
    while k:
      if k&1:
        ret = ret * n
      n = n * n
      k >>= 1
    return ret

  def __str__(self):
    return "[{}]".format("\n".join(str(row) for row in self.mat))

L, A, B, M = list(map(int, input().split()))

d = [0 for i in range(20)]
for i in range(1, 19):
  l = -1
  r = L
  while r-l>1:
    m = (l+r)//2
    if len(str(A+B*m))>i:
      r = m
    else:
      l = m
  d[i] = r

x = Matrix([[0, A, 1]], mod=M)
for i in range(1, 19):
  dt = d[i]-d[i-1]
  y = Matrix([[10**i, 0, 0], [1, 1, 0], [0, B, 1]], mod=M)
  y = y ** dt
  x *= y
print((x.mat[0][0]))


import sys
sys.setrecursionlimit(1000000)
import numpy as np
input = sys.stdin.readline

L,A,B,M = list(map(int, input().split()))

C = []
for i in range(19):
  C.append(min(max(0,(10**i - A - 1) //B + 1), L))

def R_mul(A, B, M):
  return np.mod((np.dot(A,B)), M)

def R_pow(R, n, M):
  if n == 1:
    return R
  
  R2 = R_mul(R, R, M)
  R2 = R_pow(R2, n//2, M)
  
  if n % 2 == 0:
    return R2
  else:
    return R_mul(R2, R, M)

                 
ans = 0
R = np.ones((3,3))
s = np.array([0, A%M, 1])

for d in range(1,19):
  r = C[d] - C[d-1]
  if (0 == r):
    continue
  R0 = np.array([[pow(10,d,M),1,0],[0,1,(B%M)],[0,0,1]])
  R = R_pow(R0, r, M)
  s = R_mul(R, s, M)
  #print(d, R, s)
  if (C[d] > L):
    break

print((s[0]))


#import sys
#input = sys.stdin.readline
#from numpy import matrix, eye, dot
def productMatrix(N, A, B):
    Ret = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                Ret[i][j] += A[i][k]*B[k][j]
    return Ret
def modMatrix(N, A, Q): #N×N行列のmod
    for i in range(N):
        for j in range(N):
            A[i][j] %= Q
#            A[i,j] %= Q
    return

def powOfMatrix(N, X, n, Q): #N×N行列のn乗
#    Ret = eye(N)
    Ret = [[1,0,0],[0,1,0],[0,0,1]]
    power = '{:060b}'.format(n)[::-1] #log2(pow(10,18)) < 60
    for p in power:
        if p == "1":
            Ret = productMatrix(N,Ret, X)
#            Ret = dot(Ret, X)
            modMatrix(N, Ret, Q)
        X = productMatrix(N,X,X)
#        X = dot(X,X)
        modMatrix(N, X, Q)
#        print(Ret)
    return Ret

def main():
    L, A, B, M = list(map( int, input().split()))
    s = A
    ANS = [[1,0,0],[0,1,0],[0,0,1]]
    for i in range(1, 37):
#        print(i, ANS)
        if s >= pow(10,i):
            continue
        P = [[pow(10, i, M), 0, 0], [1,1,0], [0,B,1]]
#        P = matrix([[pow(10, i, M), 0, 0], [1,1,0], [0,B,1]])
#        print((pow(10,i)-1-s)//B+1)
        step = (pow(10,i)-s+B-1)//B
        if L <= step:
            ANS = productMatrix(3,ANS,powOfMatrix(3,P,L,M))
#            ANS = dot(ANS,powOfMatrix(3,P,L,M))
            modMatrix(3,ANS,M)
            break
#        print(powOfMatrix(3,P, (pow(10,i)-1-s)//B + 1,M))
        ANS = productMatrix(3,ANS, powOfMatrix(3,P, step,M))
#        ANS = dot(ANS, powOfMatrix(3,P, (pow(10,i)-1-s)//B + 1,M))
#        print( (ANS[1][0]*A + ANS[2][0])%M, (pow(10,i)-1-s)//B + 1)
        modMatrix(3,ANS, M)
        L -= step
        s += step*B
    print(( (ANS[1][0]*A + ANS[2][0])%M))
#    print( int((ANS[1,0]*A + ANS[2,0])%M))
        
        
def __starting_point():
    main()

__starting_point()

l, a, b, MOD = [int(item) for item in input().split()]
vec = [0, a%MOD, 1]

def mat_mat_mul3(m1, m2):
    m3 = [[0] * 3 for _ in range(3)]
    for i in range(3):
        for j in range(3):
            for k in range(3):
                m3[i][j] += m1[i][k] * m2[k][j]
                m3[i][j] %= MOD
    return m3

def mat_vec_mul3(m1, v1):
    v2 = [0] * 3
    for i in range(3):
        for k in range(3):
            v2[i] += v1[k] * m1[i][k]
            v2[i] %= MOD
    return v2

A_d_pow = [[None] * 66 for _ in range(20)]
for d in range(20):
    for i in range(66):
        if i == 0:
            A = [[1, 0, 0], 
                 [0, 1, 0], 
                 [0, 0, 1]]
            A_d_pow[d][i] = A
            continue
        if i == 1:
            A = [[10**d % MOD, 1, 0], 
                 [0, 1, b % MOD], 
                 [0, 0, 1]]
            A_d_pow[d][i] = A
            continue
        A_d_pow[d][i] = mat_mat_mul3(A_d_pow[d][i-1], A_d_pow[d][i-1])

multimes = [0] * 20
for i in range(1,20):
    if 10**i > a:
        cnt = (10**i - 1 - a) // b + 1
        if cnt >= l:
            multimes[i] = l
            break
        else:
            multimes[i] = cnt
            l -= cnt
            a += cnt * b

for i, num in enumerate(multimes):
    if num == 0:
        continue
    for j in range(66):
        if num & 1 << j:
            vec = mat_vec_mul3(A_d_pow[i][j+1], vec)

print(vec[0])

L,A,B,M=map(int,input().split())
C=(L-1)*B+A
mod=M
X,s=0,A
now=A
data=[0]*19
ruiseki=[0]*19
Ami=(A-1)//B
Cmi=C//B
for i in range(19):
    now=10**i-1
    if now<A:
        ruiseki[i]=0
    elif now>=C:
        ruiseki[i]=L
    else:
        ruiseki[i]=(now-A)//B+1
def mul33(A,B):
    nonlocal mod
    res=[[0]*3 for i in range(3)]
    for i in range(3):
        for j in range(3):
            res[i][j]=sum([A[i][k]*B[k][j]%mod for k in range(3)])
    return res
def ruijou(vec,Cd):
    rui=dict()
    if Cd==0:
        return [[1,0,0],[0,1,0],[0,0,1]]
    now=vec
    ans=[[1,0,0],[0,1,0],[0,0,1]]
    Cds=bin(Cd)[2:][::-1]
    for i in range(len(Cds)):
        if Cds[i]=="1":
            ans=mul33(ans,now)
        now=mul33(now,now)
    return ans
def mul(X,s,Cd,d):
    nonlocal mod
    nonlocal B
    vec=[[pow(10,d,mod),0,0],[1,1,0],[0,B,1]]
    vec=ruijou(vec,Cd)
    Xc=X
    sc=s
    X=(Xc*vec[0][0]+sc*vec[1][0]+vec[2][0])%mod
    s=(Xc*vec[0][1]+sc*vec[1][1]+vec[2][1])%mod
    return X,s
for d in range(1,19):
    Cd=ruiseki[d]-ruiseki[d-1]
    X,s=mul(X,s,Cd,d)
print(X)

import numpy as np
def matrix_power(Mat, n):
    if n == 0:
        return I#(単位元）
    x = matrix_power(Mat, n>>1)#半分を考える
    x = np.dot(x, x)#n//2を二回行う
    if not n&1:
        return x%M
    x = np.dot(x, Mat)#あまりの分
    return x%M
I = np.identity(3, dtype = 'object') 
L, A, B, M = map(int,  input().split())
ans = np.array([[0],
                          [A],
                          [1]], dtype = 'object')
s_L = A+B*(L-1)
for digit in range(len(str(A)), len(str(s_L))+1):
    cnt = (min(s_L, 10**digit-1)-A)//B-max(-1, (10**(digit-1)-1-A)//B)
    Mat = np.array([[10**digit, 1, 0],
                            [0, 1, B],
                            [0, 0, 1]])
    ans = np.dot(matrix_power(Mat, cnt), ans)%M
print(ans[0, 0])

def mpw(n,m):
    ret=1
    while m>0:
        if m&1:
            ret*=n
            ret%=M
        n*=n
        n%=M;
        m>>=1
    return ret;
def pw(n,m):
    ret=1
    while m>0:
        if m&1:
            ret*=n
        n*=n
        m>>=1
    return ret;
def delta(i,j):
    if i==j:
        return 1
    return 0
def mtxmpw(A,m):
    ret=[[delta(i,j) for i in range(len(A))] for j in range(len(A))]
    while m>0:
        if m&1:
            ret=mul(ret,A)
        A=mul(A,A)
        m>>=1
    return ret
def mul(A,B):
    ret=[[0 for i in range(len(B[0]))] for j in range(len(A))]
    for i in range(len(A)):
        for j in range(len(B[0])):
            for k in range(len(B)):
                ret[i][j]+=A[i][k]*B[k][j]
                ret[i][j]%=M
    return ret

L,A,B,M=map(int,input().split())
ans=0
d=0
for k in range(18,0,-1):
    l=max((pw(10,(k-1))-A+B-1)//B,0)
    r=min((pw(10,k)-A-1)//B,L-1)
    if l<=r:
        MT=[[1,mpw(10,k),0],[0,mpw(10,k),(M-B*mpw(10,k)%M)%M],[0,0,mpw(10,k)]]
        v=[[(A+B*r)%M],[(A+B*(r-1)%M+M)%M],[1]]
        u=mul(mtxmpw(MT,r-l),v)
        ans+=mpw(10,d)*u[0][0]%M;
        ans%=M;
        d+=(r-l+1)*k
print(ans)

def unitmat(n):
    return [[int(i==j) for i in range(n)] for j in range(n)]
def matadd(A,B):
    h=len(A); w=len(A[0])
    C=[[A[i][j]+B[i][j] for j in range(w)] for i in range(h)]
    return C
def matmul(A,B):
    h=len(A)
    w=len(B[0])
    l=len(B)
    C=[[0]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            for k in range(l):
                C[i][j]+=A[i][k]*B[k][j]
    for i in range(h):
        for j in range(w):
            C[i][j]%=mod
    return C
def matpow(A,k):
    n=len(A)
    B=unitmat(n)
    while k:
        if k&1:
            B=matmul(B,A)
        A=matmul(A,A)
        k>>=1
    return B

l,a,b,mod=map(int,input().split())
X=[[0],[a],[1]]
maxdigit=18
Idx=[0]*(maxdigit+1)
for i in range(maxdigit+1):
    if 10**i-1<a:
        continue
    Idx[i]=min((10**i-1-a)//b+1,l)
for i in range(1,maxdigit+1):
    f=[[10**i,1,0],[0,1,b],[0,0,1]]
    X=matmul(matpow(f,Idx[i]-Idx[i-1]),X)
print(X[0][0])

import numpy as np
import sys

def II(): return int(sys.stdin.readline())
def MI(): return list(map(int, sys.stdin.readline().split()))
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

# だいたいpdfの通り
def main():
    l,a,b,md=MI()

    # 数列の要素がk桁になるのがi項目で、k+1桁になるのがj項目
    k=0
    i=0
    ans=[0,a%md,b%md]
    ans=np.array(ans,dtype="i8")
    # 各桁数ごとに処理
    while i<l:
        k+=1
        j=(10**k-a+b-1)//b
        if j<=0:continue
        if j>l:j=l
        # k桁の要素の個数がe
        e=j-i
        # i項目まで連結した整数をans[i],数列のi項目をs[i]とすると
        #                                       [10**k 0 0]
        # [ans[i],s[i],b] = [ans[i-1],s[i-1],b] [  1   1 0]
        #                                       [  0   1 1]
        # 最後の3x3行列をbbとして、e乗すればよいので、繰り返し二乗法でやる
        bb=np.zeros((3,3),dtype="i8")
        bb[0,0]=pow(10,k,md)
        bb[1,0]=bb[1,1]=bb[2,1]=bb[2,2]=1
        while e:
            if e&1:ans=np.dot(ans,bb)%md
            bb=np.dot(bb,bb)%md
            e>>=1
        i=j

    print((ans[0]))

main()



def mul_square_matrix(a, b, mod):
    n = len(a)
    ret = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                ret[i][j] = (ret[i][j] + a[i][k] * b[k][j]) % mod
    return ret


def power_square_matrix(mat:list, k, mod):
    n = len(mat)
    ret = [[0] * n for _ in range(n)]
    for i in range(n):
        ret[i][i] = 1
    while k > 0:
        if k % 2 == 1:
            ret = mul_square_matrix(ret, mat, mod)
        mat = mul_square_matrix(mat, mat, mod)
        k //= 2
    return ret

l, a, b, m = map(int, input().split())
s_foot = a + b * (l - 1)
digit_n = len(str(s_foot))
count_digit_n = [0] * (digit_n + 1)
d = 1
for i in range(1, digit_n + 1):
    d *= 10
    x = min(d - 1, s_foot) - a
    if x < 0:
        continue
    n = x // b
    count_digit_n[i] = n + 1

for i in range(digit_n, 0, -1):
    count_digit_n[i]  -= count_digit_n[i - 1]

d = 1
x = [[0], [a], [1]]
for n in count_digit_n[1:]:
    d = d * 10 % m
    if n == 0:
        continue
    mat = [[d, 1, 0], [0, 1, b], [0, 0, 1]]
    mat = power_square_matrix(mat, n, m)
    for i in range(3):
        x[i][0] = sum([mat[i][j] * x[j][0] for j in range(3)]) % m
print(x[0][0])

def matrix_product(X,Y,M):
    XY = [[0]*3 for _ in range(3)]

    for i in range(3):
        for j in range(3):
            for k in range(3):
                XY[i][j] += X[i][k]*Y[k][j] % M
            XY[i][j] %= M
    
    return XY

def power(X,n,M):
    res = [[1,0,0],[0,1,0],[0,0,1]]

    if n == 0: return res

    while n > 0:
        if n & 1: res = matrix_product(res,X,M)
        X = matrix_product(X,X,M)
        n //= 2
    
    return res

L, A, B, M = list(map(int,input().split()))

X = [0,A,1]

for d in range(1,19):
    if L == 0: break

    
    l = (10**(d-1) - A + B-1) // B
    r = (10**d - A) // B
    if (10**d - A) % B == 0: r -= 1
    
    if l < 0: l = 0
    if r < 0: r = -1
    
    C = min(r-l+1,L)
    L -= C

    Y = power([[10**d,0,0],[1,1,0],[0,B,1]],C,M)
    
    next_X = [0,0,0]
    for i in range(3):
        for j in range(3):
            next_X[i] += X[j] * Y[j][i] % M
        next_X[i] %= M
    X = next_X

print((X[0]))









L, A, B, M = map(int, input().split())
ans = 0
d = 0
def mul(X, Y):
    Z = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
    for i in range(3):
        for j in range(3):
            r = 0
            for k in range(3):
                r += X[i][k] * Y[k][j]
            Z[i][j] = r % M
    return Z

x = 0; a = A
while 1:
    kd0 = max(min((10**d - A + B - 1) // B, L), 0)
    kd1 = max(min((10**(d+1) - A + B - 1) // B, L), 0)

    Q = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
    P = [[10**(d+1), 0, 0], [1, 1, 0], [0, B, 1]]
    k = kd1 - kd0
    while k:
        if k & 1:
            Q = mul(P, Q)
        P = mul(P, P)
        k >>= 1
    x, a = (x*Q[0][0]+a*Q[1][0]+Q[2][0]) % M, (x*Q[0][1]+a*Q[1][1]+Q[2][1]) % M
    if kd1 == L:
        break
    d += 1
print(x)

def mat_prod(A, B, m):
  x = len(A)
  y = len(B)
  z = len(B[0])
  C = [[0]*z for _ in range(x)]
  for i in range(x):
    for j in range(y):
      for k in range(z):
        C[i][k] += A[i][j] * B[j][k]
        C[i][k] %= m
  return C

def mat_pow(A, n, m):
  if n == 1:
    return A
  if n%2:
    return mat_prod(mat_pow(A, n-1, m), A, m)
  B = mat_pow(A, n//2, m)
  return mat_prod(B, B, m)

L, a, b, m = map(int, input().split())
ans = 0
s = a
for k in range(1, 19):
  l = (10**(k-1)-a+b-1)//b
  r = (10**k-a+b-1)//b
  l = max(l, 0)
  r = min(r, L)
  if l >= r:
    continue
  d = r-l
  X = [[ans, s, 1]]
  Y = [[pow(10, k, m), 0, 0], [1, 1, 0], [0, b, 1]]
  Z = mat_prod(X, mat_pow(Y, d, m), m)
  ans, s = Z[0][:2]
print(ans)

import os
import sys

import numpy as np
from numpy.linalg import matrix_power

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

L, A, B, M = list(map(int, sys.stdin.readline().split()))
MOD = M


class ModInt:
    def __init__(self, value):
        self.value = value % MOD

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.value + other.value)
        else:
            return ModInt(self.value + other)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.value * other.value)
        else:
            return ModInt(self.value * other)

    def __repr__(self):
        return str(self.value)


size = 0
# 全部つなげたのを X とすると、
# [今の X, 次に加算する数, 公差]
vec = [ModInt(0), ModInt(A), ModInt(B)]
# 加算する数の桁数
digits = 1
while size < L:
    # 桁数が digits である要素の数
    # digits 以下の要素の数の合計から今までに加算した数を引く
    cnt = max(0, (10 ** digits - 1 - A) // B - size + 1)
    cnt = min(cnt, L - size)

    mat = np.array([
        [ModInt(pow(10, digits, MOD)), ModInt(0), ModInt(0)],
        [ModInt(1), ModInt(1), ModInt(0)],
        [ModInt(0), ModInt(1), ModInt(1)],
    ])
    if cnt > 0:
        vec = np.dot(vec, matrix_power(mat, cnt))
    digits += 1
    size += cnt
print((vec[0]))


l,a,b,m = map(int,input().split())

ten = 1
def f(x):

    if x == 0:
        return 0
    if x % 2 == 1:
        t = x-1
        x = f(t)
        return x*ten+1
    else:
        t = x//2
        x = f(t)
        return x*pow(ten,t,m) + x

def g(x):

    if x == 0:
        return 0
    if x % 2 == 1:
        t = x-1
        x = g(t)
        return x*ten + b*(t)
    else:
        t = x//2
        x = g(t)
        return x*pow(ten,t,m) + x + b*(t)*f(t)
last = a+b*(l-1)

ans = 0
for i in range(1,20):
    le = ten
    r = ten*10-1
    
    ten *= 10
    if last < le or a > r:
        continue
    if le < a:
        na = a
    else:
        na = (le-a+b-1)//b*b+a
    if last <= r:
        nl = last
    else:
        nl = (r-a)//b*b+a
    n = (nl-na)//b+1
    
    ans *= pow(ten,n,m)
    ans += ((f(n)%m)*na)%m
    ans += g(n)%m
    ans %= m

print(ans)

import sys
from math import log10

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 19 + 7
EPS = 10 ** -10

def bisearch_min(mn, mx, func):
    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            ok = mid
        else:
            ng = mid
    return ok

def mat_pow(mat, init, K, MOD):
    """ 行列累乗 """

    def mat_dot(A, B, MOD):
        """ 行列の積 """

        if not isinstance(A[0], list) and not isinstance(A[0], tuple):
            A = [A]
        if not isinstance(B[0], list) and not isinstance(A[0], tuple):
            B = [[b] for b in B]
        n1 = len(A)
        n2 = len(A[0])
        _ = len(B)
        m2 = len(B[0])
        res = list2d(n1, m2, 0)
        for i in range(n1):
            for j in range(m2):
                for k in range(n2):
                    res[i][j] += A[i][k] * B[k][j]
                    res[i][j] %= MOD
        return res

    def _mat_pow(mat, k, MOD):
        """ 行列matをk乗する """

        n = len(mat)
        res = list2d(n, n, 0)
        for i in range(n):
            res[i][i] = 1
        while k > 0:
            if k & 1:
                res = mat_dot(res, mat, MOD)
            mat = mat_dot(mat, mat, MOD)
            k >>= 1
        return res

    res = _mat_pow(mat, K, MOD)
    res = mat_dot(res, init, MOD)
    return [a[0] for a in res]

L, a, b, M = MAP()

A = [0] * 20
for i in range(1, 20):
    x = 10 ** i
    res = bisearch_min(-1, L, lambda m: ceil(x-a, b) <= m)
    A[i] = res
C = [0] * 20
for i in range(1, 20):
    C[i] = A[i] - A[i-1]

init = [0, a, 1]
for d in range(1, 20):
    K = C[d]
    if K == 0:
        continue
    mat = [
        # dp0[i] = dp0[i-1]*10^d + dp1[i-1]*1 + 1*0
        [pow(10, d, M), 1, 0],
        # dp1[i] = dp0[i-1]*0 + dp1[i-1]*1 + 1*b
        [0, 1, b],
        # 1 = dp0[i-1]*0 + dp1[i-1]*0 + 1*1
        [0, 0, 1],
    ]
    res = mat_pow(mat, init, K, M)
    init[0] = res[0]
    init[1] = res[1]
ans = res[0]
print(ans)

# dp0 = [0] * (L+1)
# dp1 = [0] * (L+1)
# dp0[0] = 0
# dp1[0] = a
# for i in range(1, L+1):
#     dp0[i] = (dp0[i-1]*pow(10, int(log10(dp1[i-1]))+1, M) + dp1[i-1]) % M
#     dp1[i] = dp1[i-1] + b
# ans = dp0[-1]
# print(ans)


n,a,b,MOD=list(map(int,input().split()))
def matmul(A,B):
	nonlocal MOD
	N,M,L=len(A),len(B),len(B[0])
	ret=[[0 for j in range(L)] for i in range(N)]
	for i in range(N):
		for j in range(M):
			for k in range(L):
				ret[i][k] += A[i][j]*B[j][k]%MOD
				ret[i][k] %= MOD
	return ret
ans,c=[[0,a%MOD,1]],0
for i in range(1,19):
	if not a<10**i:
		continue
	m=[[10**i%MOD,0,0],[1,1,0],[0,b%MOD,1]]
	q = -c
	c = min(((10**i-1-a)//b)+1,n)
	q += c
	while q:
		if q&1:
			ans = matmul(ans,m)
		m = matmul(m,m)
		q >>= 1
print((ans[0][0]))


L,A,B,mod=list(map(int,input().split()))

def keta(k):# k-桁の数の初項、末項、項数を求める
    if A>=10**k:
        return 0,0,0
    begin=10**(k-1)
    end=10**k

    if begin>A+B*(L-1):
        return 0,0,0

    sh=A+max(-1,(begin-1-A)//B)*B+B
    ma=min(A+max(0,(end-1-A)//B)*B,A+B*(L-1))
    kou=(ma-sh)//B+1
    
    return sh,ma,kou

from functools import lru_cache

@lru_cache(maxsize=None)
def f(n,r): # 1+r+...+r**(n-1)
    if n==1:
        return 1
    if n%2==0:
        return (f(n//2,r) + pow(r,n//2,mod)*f(n//2,r))%mod
    return (r*f(n-1,r)+1)%mod

@lru_cache(maxsize=None)
def g(n,r): # 0+r+2*r**2+...+(n-1)*r**(n-1)
    if n==1:
        return 0
    if n%2==0:
        return g(n//2,r)+pow(r,n//2,mod)*(g(n//2,r)+n//2*f(n//2,r))
    return r*g(n-1,r)+r*f(n-1,r)

keta_count=1
ANS=0
for i in range(18,0,-1):
    sh,ma,kou = keta(i)
    
    if kou<=0:
        continue
    

    #print(i,sh,ma,kou)

    ANS=(keta_count*(ma*f(kou,10**i)-B*g(kou,10**i))+ANS)%mod
    #print(ANS)
    keta_count = keta_count * pow(10,kou * i,mod)

print(ANS)
    
    


def rec(r, b, c, a0, n, mod):
    # a_n = r * a_{n-1} + b * n + c
    a = a0
    n_ = 0
    c += b
    diff = 1
    while n:
        n, m = divmod(n, 2)
        if m:
            a = (a * r + b * n_ + c) % mod
            n_ += diff
        r, b, c = r*r%mod, (r*b+b)%mod, (r*c+b*diff+c)%mod
        diff <<= 1
    return a

def main():
    L, A, B, M = list(map(int, input().split()))

    def bis(d):
        # d 桁以上になる最小の項
        n = 10**(d-1)
        ng = -1
        ok = L
        while ng + 1 < ok:
            c = ok+ng >> 1
            s_c = A + B * c
            if s_c >= n:
                ok = c
            else:
                ng = c
        return ok
    Idxs = [0]
    for d in range(1, 19):
        Idxs.append(bis(d))
    Idxs.append(L)

    ans = 0
    for d, (l, r) in enumerate(zip(Idxs, Idxs[1:])):
        if r - l == 0:
            continue
        s_l = A + B * l
        n = r - l
        ratio = 10**d
        a = rec(ratio, B, s_l, s_l, n-1, M)
        #print(d, a)
        ans = (ans * pow(10, d*n, M) + a) % M
    print(ans)

main()


from functools import reduce

L, A, B, M = list(map(int, input().split()))

MOD = M


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(
                pow(self.x, other.x, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    def __radd__(self, other):
        return ModInt(other + self.x)

    def __rsub__(self, other):
        return ModInt(other - self.x)

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))


def iceil(a, b):
    return (a + b - 1) // b


# 等差数列を桁数が同一の要素ごとに区切る
# 区切った等差数列の各要素について、それを末尾に追加する操作を線形変換とみなす
# 線形変換はダブリングで高速に計算する
T = {}
x = A
while x <= A + B * (L - 1):
    k = len(str(x))
    r = iceil(
        min(
            10**k,
            A + B * (L - 1) + 1
        ) - x,
        B
    )
    T[k] = r
    x += r * B


def mut_mul(X, Y):
    return [
        [
            sum(X[i][k] * Y[k][j] for k in range(len(Y)))
            for j in range(len(Y[0]))
        ]
        for i in range(len(X))
    ]


def mut_pow(X, n):
    if n == 0:
        return [
            [1, 0, 0],
            [0, 1, 0],
            [0, 0, 1]
        ]
    else:
        Y = mut_pow(X, n // 2)
        return (
            mut_mul(Y, Y) if n % 2 == 0 else
            mut_mul(mut_mul(Y, Y), X)
        )


def f(p, q, k, r):
    Y = mut_pow(
        [
            [ModInt(10**k), ModInt(1), ModInt(0)],
            [ModInt(0), ModInt(1), ModInt(1)],
            [ModInt(0), ModInt(0), ModInt(1)]
        ],
        r
    )
    Z = mut_mul(
        Y,
        [
            [p],
            [q],
            [ModInt(B)]
        ]
    )
    return (Z[0][0], Z[1][0])


ans, _ = reduce(
    lambda acc, kr: f(acc[0], acc[1], kr[0], kr[1]),
    sorted(T.items()),
    (ModInt(0), ModInt(A))
)

print(ans)


import sys
from math import log10

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 19 + 7
EPS = 10 ** -10

def bisearch_min(mn, mx, func):
    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            ok = mid
        else:
            ng = mid
    return ok

def mat_pow(mat, init, K, MOD):
    """ 行列累乗 """

    def mat_dot(A, B, MOD):
        """ 行列の積 """

        if not isinstance(A[0], list) and not isinstance(A[0], tuple):
            A = [A]
        if not isinstance(B[0], list) and not isinstance(A[0], tuple):
            B = [[b] for b in B]
        n1 = len(A)
        n2 = len(A[0])
        _ = len(B)
        m2 = len(B[0])
        res = list2d(n1, m2, 0)
        for i in range(n1):
            for j in range(m2):
                for k in range(n2):
                    res[i][j] += A[i][k] * B[k][j]
                    res[i][j] %= MOD
        return res

    def _mat_pow(mat, k, MOD):
        """ 行列matをk乗する """

        n = len(mat)
        res = list2d(n, n, 0)
        for i in range(n):
            res[i][i] = 1
        while k > 0:
            if k & 1:
                res = mat_dot(res, mat, MOD)
            mat = mat_dot(mat, mat, MOD)
            k >>= 1
        return res

    res = _mat_pow(mat, K, MOD)
    res = mat_dot(res, init, MOD)
    return [a[0] for a in res]

L, a, b, M = MAP()

A = [0] * 20
for i in range(1, 20):
    x = 10 ** i
    # A[i] = bisearch_min(-1, L, lambda m: ceil(x-a, b) <= m)
    A[i] = max(min(ceil(x-a, b), L), 0)
C = [0] * 20
for i in range(1, 20):
    C[i] = A[i] - A[i-1]

init = [0, a, 1]
for d in range(1, 20):
    K = C[d]
    if K == 0:
        continue
    mat = [
        # dp0[i] = dp0[i-1]*10^d + dp1[i-1]*1 + 1*0
        [pow(10, d, M), 1, 0],
        # dp1[i] = dp0[i-1]*0 + dp1[i-1]*1 + 1*b
        [0, 1, b],
        # 1 = dp0[i-1]*0 + dp1[i-1]*0 + 1*1
        [0, 0, 1],
    ]
    res = mat_pow(mat, init, K, M)
    init[0] = res[0]
    init[1] = res[1]
ans = res[0]
print(ans)

# dp0 = [0] * (L+1)
# dp1 = [0] * (L+1)
# dp0[0] = 0
# dp1[0] = a
# for i in range(1, L+1):
#     dp0[i] = (dp0[i-1]*pow(10, int(log10(dp1[i-1]))+1, M) + dp1[i-1]) % M
#     dp1[i] = dp1[i-1] + b
# ans = dp0[-1]
# print(ans)


import numpy as np
l, a, b, m = list(map(int, input().split()))
# l = 107
# a = 10000000000007  # 10**13 + 7
# b = 1000000000000007  # 10**15 + 7
# m = 998244353

s_max = a + b * (l - 1)

# ten_pow[i] = 10**i
ten_pow = [1]
while ten_pow[-1] <= s_max:
    ten_pow.append(ten_pow[-1] * 10)

# d[i] = (s_j <= 10**i - 1 なるjの数)
D_MAX = len(ten_pow)
d = [0] * D_MAX
for i in range(D_MAX):
    if ten_pow[i] >= a:
        d[i] = max((ten_pow[i] - 1 - a) // b, 0)
d[-1] = l - 1

# cd[i] = ((i+1)桁のsの要素数(s_0を除く))
cd = [d[i + 1] - d[i] for i in range(len(d) - 1)]
# print(ten_pow)
# print(d)
# print(cd)

y = np.array([a, a + b, 1]).T % m
for i in range(len(cd)):
    x = np.array([[ten_pow[i + 1] % m, 1, 0], [0, 1, b], [0, 0, 1]])
    x %= m
    # print(x)
    # print('y', y)
    k = cd[i]
    while k > 0:
        if k & 1:
            y = np.dot(x, y) % m
            # print('y', y)
        x = np.dot(x, x) % m
        k = k >> 1

ans = y[0] % m
print(ans)


l,a,b,m = list(map(int,input().split()))

# c111 -> 1001001001みたいなやつを求める
# n : 塊の数
# l : 一つの塊(00..001)の長さ
# m : mod
# ex) n=3, l=2 -> 10101
def c111(n, l, m):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n % 2 == 1:
        return (c111(n - 1, l, m) * pow(10, l, m) + 1) % m
    half = c111(n // 2, l, m)
    return (half * pow(10, (n // 2) * l, m) + half) % m

# c123 -> 1002003004みたいなやつを求める
# n : 塊の数
# l : 一つの塊(00..001)の長さ
# m : mod
# ex) n=3, l=2 -> 10203
def c123(n, l, m):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n % 2 == 1:
        return (c123(n - 1, l, m) + c111(n, l, m)) % m
    half = c123(n // 2, l, m)
    return (half * pow(10, (n // 2) * l, m) + half + (n // 2) * c111(n // 2, l, m)) % m

fst, lst = a, a + b * (l - 1)

fst_l, lst_l = len(str(fst)), len(str(lst))

res, margin = 0, 0
for keta in reversed(list(range(fst_l, lst_l + 1))):
    num_l = a + b * ((10 ** (keta - 1) - a + b - 1) // b)
    num_r = a + b * ((10 ** keta - a + b - 1) // b - 1)
    if keta == fst_l:
        num_l = fst
    if keta == lst_l:
        num_r = lst
    if num_l > num_r:
        continue
    sz = (num_r - num_l) // b + 1
    _111 = num_l * c111(sz, keta, m)
    _123 = b * c123(sz - 1, keta, m)
    res += (pow(10, margin, m) * (_111 + _123)) % m
    margin += sz * keta
print((res % m))


from operator import mul

def getMatrixProduct(Ass, Bss, MOD):
    BssTr = [list(Bs) for Bs in zip(*Bss)]  # 転置
    ansss = [[sum(map(mul, As, Bs)) % MOD for Bs in BssTr] for As in Ass]
    return ansss

def getMatrixPower(Ass, n, MOD):
    sizeA = len(Ass)
    ansss = [[0]*(sizeA) for _ in range(sizeA)]
    for i in range(sizeA):
        ansss[i][i] = 1
    while n:
        if n & 1:
            ansss = getMatrixProduct(ansss, Ass, MOD)
        Ass = getMatrixProduct(Ass, Ass, MOD)
        n //= 2
    return ansss

L, A, B, M = list(map(int, input().split()))

As = [[A%M], [A%M], [1]]
iPrev = 0
d = 1
while True:
    i = (10**d-1-A) // B
    if i > L-1:
        i = L-1
    num = i-iPrev
    if num > 0:
        Css = [[10**d,1,B%M], [0,1,B%M], [0,0,1]]
        PowCss = getMatrixPower(Css, num, M)
        As = getMatrixProduct(PowCss, As, M)
    if i == L-1:
        break
    iPrev = max(0, i)
    d += 1

print((As[0][0]))


def mmult(A, B):
    nonlocal mod
    n, m, l = len(A), len(B), len(B[0])
    ret = [[0]*l for _ in range(n)]
    for i in range(n):
        for j in range(m):
            for k in range(l):
                ret[i][k] = (ret[i][k]+A[i][j]*B[j][k])%mod
    return ret
def mpow(A, n):
    if n == 0: return [[1 if i == j else 0 for j in range(len(A))] for i in range(len(A))]
    if n % 2: return mmult(mpow(A, n-1), A)
    return mpow(mmult(A, A), n//2)

L, A, B, mod = map(int, input().split())
Y = [max((10**i-A+B-1)//B,0) for i in range(20)]
s = 0
for i in range(19):
    a, b, n = A+B*Y[i], B, max(min(L, Y[i+1])-Y[i], 0)
    M = [[10**(i+1), 0, 0], [1, 1, 0], [0, 1, 1]]
    s = mmult([[s,a,b]], mpow(M,n))[0][0]

print(s)

def f_takahashi_basics_in_education_and_learning(L, A, B, M, DIGIT_MAX=18):
    """numpyの行列演算だと L, A, B が 10**18 程度のときうまく動作しない"""
    def identity_matrix(n):
        """n×n単位行列"""
        return [[int(i == j) for i in range(n)] for j in range(n)]

    def multiply(a, b):
        """行列a, bの積"""
        row = len(a)
        col = len(b[0])
        t = len(b)
        ret = [[0] * col for _ in range(row)]
        for i in range(row):
            for j in range(col):
                for k in range(t):
                    ret[i][j] += a[i][k] * b[k][j]
        for i in range(row):
            for j in range(col):
                ret[i][j] %= M
        return ret

    def power(a, k):
        """行列aのk乗"""
        n = len(a)
        ret = identity_matrix(n)
        while k:
            if k & 1:
                ret = multiply(ret, a)
            a = multiply(a, a)
            k >>= 1
        return ret
 
    # 数列に対して、d桁の要素の個数を求める
    num_pow_d = [0] * (DIGIT_MAX + 1)
    for d in range(DIGIT_MAX + 1):
        if 10**d - 1 < A:
            continue
        # dに対してA + B*n <= 10**d - 1 となる最大のn(L以下しか取りえない)
        num_pow_d[d] = min(((10**d - 1 - A) // B) + 1, L)  # +1はnが0スタートのため
    ans = 0
    array = [[0, A, 1]]
    for d in range(1, DIGIT_MAX + 1):
        c_d = num_pow_d[d] - num_pow_d[d - 1]
        matrix = [[10**d, 0, 0], [1, 1, 0], [0, B, 1]]
        array = multiply(array, power(matrix, c_d))
    return array[0][0]

L, A, B, M = [int(i) for i in input().split()]
print(f_takahashi_basics_in_education_and_learning(L, A, B, M))

import numpy as np
import math

L, A, B, M = list(map(int, input().split()))

def f(i):
    return A+B*i

def Cd(d):
    return bisect(-1, L, d+1)-bisect(-1, L, d)

def is_ok(i, d):
    return len(str(f(i))) >= d

def bisect(ng, ok, d):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid, d):
            ok = mid
        else:
            ng = mid
    return ok


def pow_mat(a, x, p=math.inf):
    ret = np.eye(a.shape[0], dtype=int)
    tmp = a
    for i in range(x.bit_length()):
        if x >> i & 1:
            ret = np.mod(ret @ tmp, p)
        tmp = np.mod(tmp @ tmp, p)
    return ret

ret = np.eye(3, dtype=int)
for d in range(1, 19):
    a = np.array([[pow(10, d, M), 0, 0],
                  [1, 1, 0],
                  [0, B, 1]], dtype=int)
    ret = np.mod(ret @ pow_mat(a, Cd(d), M), M)
print((np.mod(np.array([0, A%M, 1]) @ ret, M)[0]))


L, a, b, m = map(int, input().split())

k = 18

c = [0] * k

t = a + b * (L - 1)

p = 9
temp = 0
for i in range(k):
    if a <= p:
        c[i] = (min(p, t) - a) // b + 1 - temp
        temp += c[i]
    if t <= p:
        break
    p = (p + 1) * 10 - 1

def calc_mat(P, Q):
    ret = [[0,0,0],[0,0,0],[0,0,0]]
    for i in range(3):
        for j in range(3):
            for k in range(3):
                ret[i][j] += P[i][k] * Q[k][j]
            ret[i][j] %= m
    return ret


s = a
x = 0
for i in range(k):
    if c[i] == 0:
        continue
    mat = [[10 ** (i + 1), 0, 0], [1,1,0], [0,b,1]]
    temp_mat = [[1,0,0],[0,1,0],[0,0,1]]
    d = list(reversed(bin(c[i])[2:]))
    p = 1
    for z in d:
        if z == '1':
            temp_mat = calc_mat(temp_mat, mat)
        mat = calc_mat(mat, mat)
    #print(temp_mat)
    temp_x = (temp_mat[0][0] * x + temp_mat[1][0] * s + temp_mat[2][0]) % m
    s = (temp_mat[0][1] * x + temp_mat[1][1] * s + temp_mat[2][1]) % m
    x = temp_x
    #print(x, s)

print(x)

l, a, b, mod = map(int, input().split())

def mul(m1, m2):
    m = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
    for i in range(3):
        for j in range(3):
            m[i][j] = sum(m1[i][k] * m2[k][j] for k in range(3)) % mod
    return m

# mat = [[1, 0, 0],                                                                                                                                                                                                                                            
#        [0, 1, 0],                                                                                                                                                                                                                                            
#        [0, 0, 1]]                                                                                                                                                                                                                                            
# vec = (0, a, 1)                                                                                                                                                                                                                                              

mat = [[0, 0, 0],
       [a, 0, 0],
       [1, 0, 0]]
d = 1
e = a + b * (l - 1)
while e >= d:
    d *= 10
    if a >= d:
        continue
    t = (min(d - 1, e) - a) // b + 1
    a += b * t
    bit = [[d, 1, 0],
           [0, 1, b],
           [0, 0, 1]]
    while t > 0:
        if t & 1:
            mat = mul(bit, mat)
        bit = mul(bit, bit)
        t //= 2

# print((mat[0][0] * vec[0] + mat[0][1] * vec[1] + mat[0][2] * vec[2]) % mod)                                                                                                                                                                                  
print(mat[0][0])

# -*- coding: utf-8 -*-
import sys
from collections import deque
import numpy as np
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    L,A,B,M=map(int,input().split())
    S=lambda i:A+B*i
    sec=[]
    
    def nibutan(ok,ng,k):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid,k):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve(mid,k):
        return len(str(S(mid)))<k
    
    left=L-1
    for k in range(19,0,-1):
        if len(str(S(left)))==k:
            right=nibutan(-1,left,k)
            sec.append((k,left,right))
            left=right
    
    X=np.array([0,A%M,1],dtype=np.int64)
    for k,left,right in sec[::-1]:
        n=left-right
        doubling=[np.array([[pow(10,k,M),0,0],[1,1,0],[0,B%M,1]],dtype=np.int64)]
        for i in range((10**18).bit_length()):
            doubling.append(np.dot(doubling[i],doubling[i])%M)
        n=left-right
        for i in range(len(doubling)):
            if n&1:
                X=np.dot(X,doubling[i])%M
            n>>=1
            if n==0:
                break
    print(X[0])

def __starting_point():
    main()

__starting_point()

import sys
input = sys.stdin.readline
#from numpy import matrix, eye, dot
def productMatrix(N, A, B):
    Ret = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                Ret[i][j] += A[i][k]*B[k][j]
    return Ret
def modMatrix(N, A, Q): #N×N行列のmod
    for i in range(N):
        for j in range(N):
            A[i][j] %= Q
    return

def powOfMatrix(N, X, n, Q): #N×N行列のn乗
    Ret = [[1,0,0],[0,1,0],[0,0,1]]
    power = '{:060b}'.format(n)[::-1] #log2(pow(10,18)) < 60
    for p in power:
        if p == "1":
            Ret = productMatrix(N,Ret, X)
            modMatrix(N, Ret, Q)
        X = productMatrix(N,X,X)
        modMatrix(N, X, Q)
    return Ret

def main():
    L, A, B, M = list(map( int, input().split()))
    s = A
    ANS = [[1,0,0],[0,1,0],[0,0,1]]
    for i in range(1, 37):
        if s >= pow(10,i):
            continue
        P = [[pow(10, i, M), 0, 0], [1,1,0], [0,B,1]]
        step = (pow(10,i)-s+B-1)//B
        if L <= step:
            ANS = productMatrix(3,ANS,powOfMatrix(3,P,L,M))
            modMatrix(3,ANS,M)
            break
        ANS = productMatrix(3,ANS, powOfMatrix(3,P, step,M))
        modMatrix(3,ANS, M)
        L -= step
        s += step*B
    print(( (ANS[1][0]*A + ANS[2][0])%M))

def __starting_point():
    main()

__starting_point()

L,A,B,M=list(map(int,input().split()))
K=19
gap=[-1 for k in range(K)]
for k in range(K):
    tmp=10**k-A
    if tmp%B==0:
        gap[k]=-1+tmp//B
    else:
        gap[k]=tmp//B
    gap[k]=min(L-1,gap[k])
    gap[k]=max(-1,gap[k])
num=[0 for k in range(K)]
for k in range(1,K):
    #k-1,k
    num[k]=-gap[k-1]+gap[k]
def matrix(d):
    return [[pow(10,d,M),1,0],[0,1,B],[0,0,1]]
def mattime(P,Q):
    R=[[0,0,0],[0,0,0],[0,0,0]]
    for i in range(3):
        for j in range(3):
            for k in range(3):
                R[i][j]+=P[i][k]*Q[k][j]
                R[i][j]%=M
    return R
def matexp(P,n):
    if n==0:
        return [[1,0,0],[0,1,0],[0,0,1]]
    elif n%2==0:
        return matexp(mattime(P,P),n//2)
    else:
        return mattime(P,matexp(mattime(P,P),n//2))
Mat=[[1,0,0],[0,1,0],[0,0,1]]
for d in range(1,K):
    Mat=mattime(matexp(matrix(d),num[d]),Mat)
print(((A*Mat[0][1]+Mat[0][2])%M))


import sys
sys.setrecursionlimit(pow(10, 6))
# input = sys.stdin.readline

import numpy as np

def pow_matmul(r, n, m):
  if n == 1:
    return r
  if n % 2 == 0:
    _r = pow_matmul(r, n//2, m)
    return np.mod(np.dot(_r, _r), m)
  else:
    _r = pow_matmul(r, n//2, m)
    _r = np.mod(np.dot(_r, _r), m)
    return np.mod(np.dot(r, _r), m)

def main():
  l, a, b, m = list(map(int, input().split()))
  c = [min(max(0, (10**i - a - 1) // b + 1), l) for i in range(19)]
  ans = 0
  r = np.ones((3,3))
  s = np.array([0, a%m, 1])

  for d in range(1, 19):
    dnum = c[d] - c[d-1]
    if dnum==0:
      continue
    r_s = np.array([[pow(10, d, m), 1, 0], [0, 1, (b%m)], [0, 0, 1]])
    r = pow_matmul(r_s, dnum, m)
    s = np.mod(np.dot(r, s), m)
    if c[d] > l:
      break
  print((s[0]))


def __starting_point():
  main()

__starting_point()

import numpy as np


def exp_np(a, e, m):
    r = np.identity(a.shape[0], dtype=np.int64)
    t = a.copy()
    while e:
        if e % 2:
            r = np.dot(r, t) % m
        t = np.dot(t, t) % m
        e >>= 1
    return r


l, a, b, m = list(map(int, input().split()))

first_d = len(str(a))
tail = a + b * (l - 1)

lo = -1
state = np.array([[0, a % m, 1]])

for d in range(first_d, 19):
    hi = min((10 ** d - 1 - a) // b, l - 1)
    cnt = hi - lo
    coe = np.array([
        [pow(10, d, m), 0, 0],
        [1, 1, 0],
        [0, b % m, 1]
    ], dtype=np.int64)

    coe = exp_np(coe, cnt, m)
    state = np.dot(state, coe) % m

    lo = hi
    if hi == l - 1:
        break

print((state[0][0]))


import numpy as np

L, A, B, M = (int(i) for i in input().split())
keta = [0] * 18
for i in range(18):
    keta[i] = min((10**i - A - 1)//B, L-1)
keta.reverse()
for i in range(18):
    if keta[i] < 0:
        keta[i] = -1
        break
keta.reverse()

def power(g, N, M):
    if N == 0:
        g = np.array([1, 0, 0, 0, 1, 0, 0, 0, 1]).reshape(3, 3)
    elif N == 1:
        pass
    elif N%2 == 0:
        g = np.linalg.matrix_power(power(g, N//2, M), 2)
    elif N%2 == 1:
        g = np.dot(g, power(g, N-1, M))
    return g%M

ans = 0
for i in range(18):
    N = i + 1
    mi = keta[i] + 1
    if mi < 0:
        continue
    if i != 17:
        ma = keta[i+1]
    else:
        ma = L-1
    if mi >= L:
        break
    t = np.array([ans, (A + B*mi)%M, 1])
    g = np.array([10**N%M, 0, 0, 1, 1, 0, 0, B%M, 1]).reshape(3, 3)
    g = power(g, ma-mi+1, M)
    g = np.dot(t, g)
    ans = g[0]%M
print(ans)

import math, itertools

L, A, B, mod = [int(_) for _ in input().split()]


def sum_ri(r, n, mod):
    #1,r,...,r**(n-1)
    if r == 1:
        return n % mod
    else:
        #(r**n-1)/(r-1)=Q*mod+R
        #R**n-1=Q*mod*(r-1)+R*(r-1)
        return (pow(r, n, mod * (r - 1)) - 1) // (r - 1) % mod


def sum_iri(r, n, mod):
    #0,1*r,...,(n-1)*r**(n-1)
    if r == 1:
        return n * (n - 1) // 2 % mod
    else:
        r1 = r - 1
        p = pow(r, n, mod * r1**2)
        ret = (n - 1) * p * r1 + r1 - (p - 1)
        ret //= r1**2
        ret %= mod
        return ret


ans = 0

for digit in range(1, 20):
    #digit桁の総和
    #10**(digit-1)<=A+B*i<10**digit
    #(10**(digit-1)-A-1)//B+1<=i<=(10**digit-A-1)//B
    ileft = max(0, (10**(digit - 1) - A - 1) // B + 1)
    iright = min(L - 1, (10**digit - A - 1) // B)
    if L <= ileft:
        break
    if ileft > iright:
        continue
    idiff = iright - ileft + 1
    #ileft<=i<=iright
    #sum(ileft,iright) (A+B*i)10**(digit*(iright-i))
    #sum(0,iright-ileft)(A+B*iright-B*j))*(10**digit)**j
    pow10digit = pow(10, digit, mod)
    now = (A + B * iright) * sum_ri(pow10digit, idiff, mod)
    now -= B * sum_iri(pow10digit, idiff, mod)
    ans *= pow(10, digit * idiff, mod)
    ans += now
    ans %= mod
print(ans)


from numpy.linalg import matrix_power
from numpy import dot, array

class mint:
    def __init__(self, n):
        self.n = n % mod

    def __add__(self, other):
        return mint(self.n + other.n)

    def __mul__(self, other):
        return mint(self.n * other.n)

    def __repr__(self):
        return str(self.n)


L, A, B, mod = map(int, input().split())

ans = array([mint(0), mint(A), mint(B)])

size = 0
for d in range(1, 19):
    x = pow(10, d, mod)
    T = array([
        [mint(x), mint(0), mint(0)],
        [mint(1), mint(1), mint(0)],
        [mint(0), mint(1), mint(1)],
    ])

    cnt = min(L - size, max(0, 10 ** d - 1 - A) // B - size + 1)
    if cnt > 0:
        ans = dot(ans, matrix_power(T, cnt))

    size += cnt
    if size >= L:
        break

print(ans[0])

#!/usr/bin/env python3

MOD = None

def matunit(n):
    return [ [ int(y == x) for x in range(n) ] for y in range(n) ]

def matadd(a, b):
    assert len(a) == len(b)
    assert len(a[0]) == len(b[0])
    h = len(a)
    w = len(a[0])
    c = [ [ a[y][x] + b[y][x] for x in range(w) ] for y in range(h) ]
    return c

def matmul(a, b):
    assert len(a[0]) == len(b)
    h = len(a)
    k = len(b)
    w = len(b[0])
    c = [ [ 0 for _ in range(w) ] for _ in range(h) ]
    for y in range(h):
        for z in range(k):
            for x in range(w):
                c[y][x] += a[y][z] * b[z][x]
    for y in range(h):
        for x in range(w):
            c[y][x] %= MOD
    return c

def matpow(a, k):
    assert len(a) == len(a[0])
    n = len(a)
    b = matunit(n)
    while k:
        if k & 1:
            b = matmul(b, a)
        a = matmul(a, a)
        k >>= 1
    return b

def binsearch(l, r, pred): # [l, r)
    assert l < r
    l -= 1
    while r - l > 1:
        m = (l + r) // 2
        if pred(m):
            r = m
        else:
            l = m
    return r

def main():
    l, a, b, m = list(map(int, input().split()))

    nonlocal MOD
    MOD = m

    x = [ [ 0 ], [ a ], [ 1 ] ]  # (answer, s_i, 1)
    DIGITS = 20
    d = [ binsearch(0, l, lambda i: len(str(a + b * i)) >= d) for d in range(DIGITS) ]
    for i in range(DIGITS - 1):
        l = d[i]
        r = d[i + 1]
        f = [ [ 10 ** i, 1, 0 ], [ 0, 1, b ], [ 0, 0, 1 ] ]
        x = matmul(matpow(f, r - l), x)
    print((x[0][0] % m))


def __starting_point():
    main()

__starting_point()

# Atcoder Problem Solving
# F - Takahashi's Basics in Education and Learning
import math
L, A, D, mod = map(int, input().split())
que = []

ans = 0
# 1桁、......20桁のグループに分類する
for i in range(1, 22):
    #10**(i-1) <= A+D*(j) < 10**(i)
    if (10**(i-1)-A+D) % D == 0:
        lowest = max(1, (10**(i-1)-A+D)//D)
    else:
        lowest = max(1, (10**(i-1)-A+D)//D+1)
    highest = 0
    if (10**i-A+D) % D == 0:
        highest = min((10**i-A+D)//D-1, L)

    else:
        highest = min((10**i-A+D)//D, L)

    if 1 <= lowest <= highest:
        que.append((i, lowest, highest))


def poly_sum(X, N, mod):
    # return X^N +    .... X^1+1 mod
    # O(logN)
    if N == 0:
        return 1
    if N == 1:
        return (X+1) % mod
    else:
        if N % 2 == 0:
            tmp_res = poly_sum(X, N//2, mod)
            return ((pow(X, N//2, mod)+1)*tmp_res-pow(X, N//2, mod)) % mod

        elif N % 2 != 0:
            tmp_res = poly_sum(X, N//2, mod)
            return (pow(X, N//2+1, mod)+1)*tmp_res % mod


def sum_of_poly_sum(X, N, mod):
    # return poly_sum(X,N,mod)+ poly_sum(X,N-1,mod) +poly_sum(X,N-2,mod) +.....  + poly_sum(X,1,mod) + poly_sum(X,0,mod)
    # O(logN*logN)
    if N == 0:
        return poly_sum(X, 0, mod)
    elif N == 1:
        return (poly_sum(X, 1, mod)+poly_sum(X, 0, mod)) % mod
    else:
        return ((sum_of_poly_sum(X, (N-1)//2, mod))*(pow(X, N//2+1, mod)+1)+(N//2+1)*poly_sum(X, N//2, mod)) % mod


def find_mod(length, lowest, highest, mod):
    # length 桁　の lowest 項目から highest 項目における連結巨大数のmodular
    X = pow(10, length, mod)
    if highest > lowest:
        base = (A+D*(lowest-1))*poly_sum(X, highest-lowest, mod) + \
            D*sum_of_poly_sum(X, highest-lowest - 1, mod)
    elif highest == lowest:
        base = A+D*(lowest-1)
    return base % mod


que.reverse()

digits = 0
for length, lowest, highest in que:
    ans += find_mod(length, lowest, highest, mod)*pow(10, digits, mod)
    ans %= mod
    digits += length*(highest+1-lowest)

print(ans % mod)

def S1(r,T,M):
  # 1+r+...+r^{T-1}
  # (r^T-1)/(r-1)
  # mod M(r-1)で計算する
  if r == 1:
    return T%M
  x = pow(r,T,M*(r-1)) - 1
  return (x//(r-1))%M

def S2(r,T,M):
  # sum ir^i
  if r == 1:
    x = T*(T-1)//2
    return x%M
  Mr = M*(r-1)
  x = (T-1) * pow(r,T,Mr)
  x -= S1(r,T,Mr)
  x += 1
  x //= (r-1)
  return x

def S(A,B,L,M):
  result = 0
  d = len(str(A)) # 桁数
  start = A
  r = 10**d
  while True:
    n1 = ((r-1)-A)//B+1
    items = min(n1,L) # その桁の項数
    last = A + (items-1)*B
    x = last * S1(r,items,M)
    x -= B * S2(r,items,M)
    result *= pow(r,items,M)
    result += x
    result %= M
    # パラメータの更新
    r *= 10
    d += 1 # 不要かも
    L -= items
    A += B*items
    if L <= 0:
      break
  return result%M

L,A,B,M = map(int,input().split())
answer = S(A,B,L,M)
print(answer)

import math
import sys
sys.setrecursionlimit(10000)

def nasu(A, B, L, D, M):
  if L == 1:
    return A
  ans = nasuA(A, L, D, M)
  ans = (ans + nasuB(1, L - 1, D, M) * B * D) % M
  return ans % M

def nasuB(B, L, D, M):
  if L == 1:
    return B
  ans = powB(1, L, D, M) % M
  return ans % M

def powB(B, L, D, M):
  if L == 1:
    return B
  k = 0
  t = D
  while T[k + 1] <= L:
    k += 1
    t = t * t % M
    if k + 1 == len(T):
      break
  ans = powB2(B, T[k], D, M) % M
  if L != T[k]:
    ans += nasu(T[k] + 1, 1, L - T[k], D, M) * t % M 
    #ans += powB(1, L - T[k], D, M) * t % M
    #ans += powA(-T[k], L - T[k], D, M) * t % M
  return ans % M
 
def powB2(B, L, D, M):
  if L == 1:
    return 1
  ans = powB2(B * 2, L // 2, D * D % M, M) * (D + 1) % M
  ans = ans + nasuA(1, L // 2, D * D % M, M) * B * D % M
  return ans

def nasuA(A, L, D, M):
  if L == 1:
    return A
  ans = powA(A, L, D, M) % M
  return ans % M

def powA(A, L, D, M):
  if L == 1:
    return A
  k = 0
  t = D
  while T[k + 1] <= L:
    k += 1
    t = t * t % M
    if k + 1 == len(T):
      break
  ans = powA2(A, T[k], D, M)
  if L != T[k]:
    ans +=  powA(A, L - T[k], D, M) * t % M
  return ans % M
 
def powA2(A, L, D, M):
  if L == 1:
    return A
  return powA2(A, L // 2, D * D % M, M) * (D + 1) % M

def powmod(a, n, M):
  ans = 1
  while n:
    if n & 1:
      ans = (ans * a) % M
    a = a * a % M
    n >>= 1
  return ans

L, A, B, M = list(map(int, input().split()))

N = math.ceil(math.log(A + 1, 10))
k = pow(10, N)
D = [[0, 0] for _ in range(20)]
while L > 0:
  n = min(L, (k - 1 - A) // B + 1)
  D[N - 1][0] = A
  D[N - 1][1] = n
  L -= n
  N += 1
  k *= 10
  A += n * B
T = [1]
while T[-1] < 10 ** 19:
  T.append(T[-1] * 2)
BI = (((B // M) + 1) * M - B) % M
ans = 0
for i in range(20):
  l = D[i][1]
  a = D[i][0] + (l - 1) * B
  if l == 0:
    continue
  ans = ans * powmod(pow(10, i + 1), l, M) % M
  ans = (ans + nasu(a, BI, l, pow(10, i + 1), M)) % M
print(ans)

import sys
import time

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    import numpy as np
    l, a, b, m = list(map(int, readline().split()))
    d_min = len(str(a))
    d_max = len(str(a + (l - 1) * b))
    count_d = [-1] * 19

    prev = -1
    for i in range(d_min, d_max + 1):
        power = 10 ** i
        ok = 0
        ng = l + 1
        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            x = a + mid * b
            if x < power:
                ok = mid
            else:
                ng = mid
        ok = min(ok, l - 1)
        count_d[i] = ok - prev
        prev = ok

    res = np.array([0, a, 1], dtype="int64")
    res = np.mod(res, m)

    for i in range(19):
        count = count_d[i]
        if count == -1:
            continue
        mat = np.array([[10 ** i, 0, 0],
                        [1, 1, 0],
                        [0, b, 1]], dtype="int64")
        mat = np.mod(mat, m)
        cur = np.eye(3, dtype="int64")
        count_bit = format(count, "b")
        for bit in count_bit[::-1]:
            if bit == "1":
                cur = np.dot(cur, mat)
                cur = np.mod(cur, m)
            mat = np.dot(mat, mat)
            mat = np.mod(mat, m)
        res = np.dot(res, cur)
        res = np.mod(res, m)

    print((res[0]))


def __starting_point():
    main()

__starting_point()

import sys
sys.setrecursionlimit(100000000)

def mult(A, B, mod): #行列A, Bの内積を求める。
    D = [[(A[0][0] * B[0][0]) % mod, 0, 0], [0, 1, 0], [0, 0, 1]]
    D[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % mod
    D[2][0] = (A[2][0]*B[0][0]+A[2][1]*B[1][0]+A[2][2]*B[2][0]) % mod
    D[2][1] = (A[2][1]*B[1][1]+A[2][2]*B[2][1]) % mod
    return D

def double(C, mod):
    D = [[pow(C[0][0], 2, mod), 0, 0], [(C[1][0] * C[0][0] + C[1][0]) % mod, 1, 0], [(C[2][0] * C[0][0] + C[2][1] * C[1][0] + C[2][0]) % mod, (C[2][1] * 2) % mod, 1]]
    return D

def Cpow(C, n, mod):
    if n == 1: return C
    else:
        D = double(C, mod)
        if n % 2 == 0:
            return Cpow(D, n // 2, mod)
        else:
            return mult(Cpow(D, n // 2, mod), C, mod)

def solve():
    L, a, b, M = map(int, input().split())
    X = 0
    s = a
    nd = -1
    ne = 0
    for d in range(1, 19):
        ne = min((pow(10, d) - a - 1) // b, L-1)
        if ne < 0: continue
        elif ne == nd: continue
        C = [[pow(10, d, M), 0, 0], [1, 1, 0], [0, b % M, 1]]
        D = Cpow(C, ne - nd, M)
        X = (X * D[0][0] + D[1][0] * s + D[2][0]) % M
        s += D[2][1]
        if ne == L - 1: break
        nd = ne
    print(X)
    return

def __starting_point():
    solve()
__starting_point()

L, A, B, M = list(map(int, input().split()))

ten = 0

def pow_(x, t):
  if t == 0:
    return 1
  if t % 2 == 1:
    return (pow_(x, t - 1) * x) % M
  else:
    y = pow_(x, t // 2)
    return (y * y) % M

def f(l):
  if l == 0:
    return 0
  if l % 2 == 1:
    pl = l - 1
    x = f(pl)
    return x * ten + 1
  else:
    pl = l // 2
    x = f(pl)
    return x * pow_(ten, pl) + x

def g(l):
  if l == 0:
    return 0
  if l % 2 == 1:
    pl = l - 1
    x = g(pl)
    return x * ten + B * pl
  else:
    pl = l // 2
    x = g(pl)
    return x * pow_(ten, pl) + x + B * pl * f(pl)

last = A + B * (L - 1)
ans = 0
ten = 10
for _ in range(18):
  l = ten // 10
  r = ten - 1
  
  if last < l:
    ten *= 10
    continue
  if A > r:
    ten *= 10
    continue
  na = 0 #初項
  nl = 0 #長さ

  if A >= l:
    na = A
  else:
    na = (l - A + B - 1) // B * B + A
    na = min(na, last)
  
  nlast = 0
  if last <= r:
    nlast = last
  else:
    nlast = (r - A) // B * B + A
  nl = (nlast - na) // B + 1

  ans *= pow_(ten, nl) % M
  ans += (na * f(nl)) % M
  ans += g(nl) % M
  ten *= 10

print((ans % M))


L,A,B,M=map(int,input().split())
MOD=M

#n*n行列の積を繰り返し二乗法で求める
#単位行列
def imat(n):
  ret=[[1 if i==j else 0 for j in range(n)] for i in range(n)]
  return ret

#行列の積A*B
def prod_mat(amat,bmat):
  res_mat = [[sum([amat[i][j]*bmat[j][k] for j in range(len(bmat))]) for k in range(len(bmat[0]))] for i in range(len(amat))]
  return res_mat  

def powmod_mat(amat,p):
  if p==0:
    return imat(len(amat))
  else:
    pow2=powmod_mat(amat,p//2)
    if p%2==0:
      res_mat=prod_mat(pow2,pow2)
    else:
      res_mat=prod_mat(amat,prod_mat(pow2,pow2))

    for i in range(len(amat)):
      for j in range(len(amat)):
        res_mat[i][j]%=MOD
    return res_mat

slist=[]
for d in range(1,19):
  s=-(-(10**d-A)//B)
  if s>=0:
    slist.append(min(s,L))
  else:
    slist.append(0)
#print(slist)

dlist=[slist[0]]
for d in range(1,18):
  dlist.append(slist[d]-slist[d-1])
#print(dlist)

mat=imat(3)
for d in range(18):
  e=dlist[d]
  pmat=powmod_mat([[10**(d+1),1,0],[0,1,B],[0,0,1]],e)
  mat=prod_mat(pmat,mat)
  for i in range(3):
    for j in range(3):
      mat[i][j]%=MOD

#init
vec=[[0],[A],[1]]
vec=prod_mat(mat,vec)
print(vec[0][0]%MOD)

from numpy.linalg import matrix_power
from numpy import dot

class mint:
    def __init__(self, n):
        self.n = n % mod

    def __add__(self, other):
        return mint(self.n + other.n)

    def __mul__(self, other):
        return mint(self.n * other.n)

    def __repr__(self):
        return str(self.n)


L, A, B, mod = map(int, input().split())

ans = [mint(0), mint(A), mint(B)]

size = 0
for d in range(1, 19):
    x = pow(10, d, mod)
    T = [
        [mint(x), mint(0), mint(0)],
        [mint(1), mint(1), mint(0)],
        [mint(0), mint(1), mint(1)],
    ]

    cnt = min(L - size, max(0, 10 ** d - 1 - A) // B - size + 1)
    if cnt > 0:
        ans = dot(ans, matrix_power(T, cnt))

    size += cnt
    if size >= L:
        break

print(ans[0])

import sys
from math import log10

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 19 + 7
EPS = 10 ** -10

def bisearch_min(mn, mx, func):
    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            ok = mid
        else:
            ng = mid
    return ok

def mat_pow(mat, init, K, MOD):
    """ 行列累乗 """

    def mat_dot(A, B, MOD):
        """ 行列の積 """

        if not isinstance(A[0], list) and not isinstance(A[0], tuple):
            A = [A]
        if not isinstance(B[0], list) and not isinstance(A[0], tuple):
            B = [[b] for b in B]
        n1 = len(A)
        n2 = len(A[0])
        _ = len(B)
        m2 = len(B[0])
        res = list2d(n1, m2, 0)
        for i in range(n1):
            for j in range(m2):
                for k in range(n2):
                    res[i][j] += A[i][k] * B[k][j]
                    res[i][j] %= MOD
        return res

    def _mat_pow(mat, k, MOD):
        """ 行列matをk乗する """

        n = len(mat)
        res = list2d(n, n, 0)
        for i in range(n):
            res[i][i] = 1
        while k > 0:
            if k & 1:
                res = mat_dot(res, mat, MOD)
            mat = mat_dot(mat, mat, MOD)
            k >>= 1
        return res

    res = _mat_pow(mat, K, MOD)
    res = mat_dot(res, init, MOD)
    return [a[0] for a in res]

L, a, b, M = MAP()

A = [0] * 20
for i in range(1, 20):
    x = 10 ** i
    res = bisearch_min(-1, L, lambda m: ceil(x-a, b)-1 < m)
    A[i] = res
C = [0] * 20
for i in range(1, 20):
    C[i] = A[i] - A[i-1]

init = [0, a, 1]
for d in range(1, 20):
    K = C[d]
    if K == 0:
        continue
    mat = [
        [pow(10, d, M), 1, 0],
        [0, 1, b],
        [0, 0, 1],
    ]
    res = mat_pow(mat, init, K, M)
    init[0] = res[0]
    init[1] = res[1]
ans = res[0]
print(ans)

# dp0 = [0] * (L+1)
# dp1 = [0] * (L+1)
# dp0[0] = 0
# dp1[0] = a
# for i in range(1, L+1):
#     dp0[i] = (dp0[i-1]*pow(10, int(log10(dp1[i-1]))+1, M) + dp1[i-1]) % M
#     dp1[i] = dp1[i-1] + b
# ans = dp0[-1]
# print(ans)