Problem: 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?

Submission attempts (in order):
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]]

    #for j in range(cd_2[i]):
    n = cd_2[i]
    while n > 0:
        print(n)
        if n & 1:

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

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

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

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

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

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

        print(A)
        n = n >> 1

    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)



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)


Verdicts: Wrong Answer

Accepted