Problem:


Score : 600 points

Problem Statement
Q tuples of integers (L_i, A_i, B_i, M_i). 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 1

5 3 4 10007

Sample Output 1

5563

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

Sample Input 2

4 8 1 1000000

Sample Output 2

891011

Sample Input 3

107 10000000000007 1000000000000007 998244353

Sample Output 3

39122908



Sample input:
5 3 4 10007


Sample output:
5563

Submission status: Time Limit Exceeded

Solution code:
L,A,B,M=map(int,input().split())
ans=(B*(L-1)+A)%M
ima=B*(L-1)+A
keta=len(str(ima))
for i in range(L-1):
  ima-=B
  ans+=pow(10,keta,M)*ima
  ans%=M
  keta+=len(str(ima))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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] = min((int('9' * (i + 1)) - A) // B + 1, 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])

Submission status: Time Limit Exceeded

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

arr=[str(A+B*i) for i in range(L)]

brr="".join(arr)


print(int(brr)%M)

Submission status: Time Limit Exceeded

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

def pow(e,p):
    b = e
    ret = 1
    while p > 0:
        if p % 2:
            ret *= b
            ret %= m
        b = b * b
        b %= m
        p //= 2
    return ret

def powow(n,p):
    b = n
    ret = 1
    while p > 0:
        if p % 2:
            ret *= b
        b = b * b
        p //= 2
    return ret

def sol(be,en,le,po):
    ll = len(str(be))
    ret = (en*(powow(10,ll*le)-1)//(10**ll-1))%m
    minus = b*((10**ll-powow(10,ll*le)-(le-1)*(powow(10,ll*le))+(le-1)*(powow(10,ll*(le+1))))//(10**ll-1)//(10**ll-1)) % m
    ret = ret + m - minus
    return ret * po % m

def last(be):
    ub = 1
    while ub <= be:
        ub *= 10
    ubb = be + (ub-be-1)//b*b

    return [be,min(ubb,a+b*(l-1)),min((ubb-be)//b+1,(a+b*(l-1)-be)//b+1)]

arr = []
be = a
while (be - a)//b < l:
    arr = [last(be)] + arr
    be = arr[0][1] + b


ret = 0
po = 1
for a in arr:
    ret += sol(a[0],a[1],a[2],po)
    po *= pow(10,(len(str(a[0]))*a[2]))
    po %= m
    ret %= m
print(ret)

Submission status: Time Limit Exceeded

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

def pow(e,p):
    b = e
    ret = 1
    while p > 0:
        if p % 2:
            ret *= b
            ret %= m
        b = b * b
        b %= m
        p //= 2
    return ret

def sol(be,en,le,po):
    ll = len(str(be))
    ret = (en*(10**(ll*le)-1)//(10**ll-1))%m
    minus = b*((10**ll-10**(ll*le)-(le-1)*(10**(ll*le))+(le-1)*(10**(ll*(le+1))))//(10**ll-1)//(10**ll-1)) % m
    ret = ret + m - minus
    return ret * po % m

def last(be):
    ub = 1
    while ub <= be:
        ub *= 10
    ubb = be + (ub-be-1)//b*b

    return [be,min(ubb,a+b*(l-1)),min((ubb-be)//b+1,(a+b*(l-1)-be)//b+1)]

arr = []
be = a
while (be - a)//b < l:
    arr = [last(be)] + arr
    be = arr[0][1] + b


ret = 0
po = 1
for a in arr:
    ret += sol(a[0],a[1],a[2],po)
    po *= pow(10,(len(str(a[0]))*a[2]))
    po %= m
    ret %= m
print(ret)

Submission status: Time Limit Exceeded

Solution code:
l, a, b, m = map(int, input().split())
ans = 0
for k in range(a, a + b * l, b):
    ans = (ans * pow(10, len(str(k)), m) + k) % m
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

def II(): return int(sys.stdin.readline())
def MI(): return 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
    cc=np.eye(3,dtype="i8")
    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()

Submission status: Time Limit Exceeded

Solution code:
import sys

def II(): return int(sys.stdin.readline())
def MI(): return 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():
    def dot(aa, bb):
        h = len(aa)
        w = len(bb[0])
        res = [[0] * w for _ in range(h)]
        for i, row in enumerate(aa):
            for j, col in enumerate(zip(*bb)):
                res[i][j] = sum(a * b % md for a, b in zip(row, col)) % md
        return res

    l, a, b, md = MI()

    # 数列の要素がk桁になるのがi項目で、k+1桁になるのがj項目
    k = 0
    i = 0
    cc = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
    # 各桁数ごとに処理
    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 = [[pow(10, k, md), 0, 0], [1, 1, 0], [0, 1, 1]]
        while e:
            if e & 1: cc = dot(cc, bb)
            bb = dot(bb, bb)
            e >>= 1
        i = j

    # bbの累乗からできたccを初期値にかけて、答えを出す
    ans = [[0, a % md, b % md]]
    ans = dot(ans, cc)
    print(ans[0][0])

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return 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
    cc=np.eye(3,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:cc=np.dot(cc,bb)%md
            bb=np.dot(bb,bb)%md
            e>>=1
        i=j

    # bbの累乗からできたccを初期値にかけて、答えを出す
    ans=[0,a%md,b%md]
    ans=np.array(ans,dtype="i8")
    ans=np.dot(ans,cc)%md
    print(ans[0])

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return 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
    cc=np.eye(3,dtype=np.object)
    # 各桁数ごとに処理
    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=np.object)
        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:cc=np.dot(cc,bb)%md
            bb=np.dot(bb,bb)%md
            e>>=1
        i=j

    # bbの累乗からできたccを初期値にかけて、答えを出す
    ans=[0,a,b]
    ans=np.array(ans,dtype=np.object)
    ans=np.dot(ans,cc)%md
    print(ans[0])

main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
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
    
    def modinv(a, mod=M):
        b,u,v = mod,1,0
        while b:
            t=a//b
            a-=t*b
            a,b=b,a
            u-=t*v
            u,v=v,u
        u%=mod
        if u < 0:
            u+=mod
        return u
    
    
    ans=0
    c=0
    for k,left,right in sec:
        C=pow(10,k)
        n=left-right
        ans+=(S(left)*(pow(C,n)-1)-B*((n-1)*pow(C,n)-(pow(C,n)-1)//(C-1)+1))//(C-1)*pow(10,c)
        ans%=M
        c+=n*k
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
L, A, B, M = [int(s) for s in input().split()]

s = ''

for i in range(L):
    s += str(A+B*i)
    
print(int(s) % M)

Submission status: Time Limit Exceeded

Solution code:
import math

L, A, B, M = list(map(int, input().split()))
rest = [1]
for i in range(19):
    rest.append(rest[i] * 10 % M)

ord_mod = 1
ans = 0
for i in range(L - 1, -1, -1):
    v = A + B * i
    ord = int(math.log10(v))
    v %= M
    ans = (ans + ((v % M) * ord_mod % M) % M) % M
    ord_mod = ((ord_mod % M) * rest[ord + 1]) % M
print(ans)

Submission status: Time Limit Exceeded

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/abc129/tasks/abc129_f

Lが大きいので全探索は不可能
等差数列の桁数ごとに考える？

うしろから考えたほうがよさそうだ？
終項XはA+B*(L-1)　公差は-B の数列t0t1…と考えられる
桁数がkの所だけ考えると寄与の数列u0u1…は

========考察完了=========
桁別に分けて考える
まず桁数がkの奴がいくつあるか、最大の項は何か、それ以前に何桁あるか、が必要
→大きい方から見ていくか

あとは、桁ごとに寄与を計算し、式変形頑張れば解ける
"""

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

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

uzero = A+B*(L-1) #u0
ldig  = 0         #u0以前にいくつ桁が存在するか
dignum = len(str(uzero)) #uzeroの桁数

ans = 0
while True:

    if A > uzero: #Aより小さいなら飛ばす
        break
    
    #nは項数
    if 10**(dignum-1) <= A:
        n = (uzero-A)//B+1
    else:
        n = (uzero-A)//B - ((10**(dignum-1)-1)-A)//B


    S = (pow(10,n*dignum)-1) // (pow(10,dignum)-1)
    S %= mod

    Sd = (n-1)*pow(10,n*dignum)-(pow(10,dignum)*(pow(10,(n-1)*dignum)-1)//(pow(10,dignum)-1))
    Sd //= (pow(10,dignum)-1)
    Sd %= mod

    ans += uzero * S * pow(10,ldig,mod) - B * pow(10,ldig,mod)*Sd
    ans %= mod

    #print (uzero , ldig , n ,uzero * S , B * pow(10,ldig,mod)*Sd % mod)

    ldig += dignum * n
    uzero -= B*n
    dignum = len(str(uzero))

print (ans)

Submission status: Time Limit Exceeded

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

S=[]
for i in range(L):
    S +=[A+B*i]
T=S[0]
for i in range(1,L):
    T= T*10**len(str(S[i]))+S[i]
print(T%M)

Submission status: Time Limit Exceeded

Solution code:
import unittest


class TestF(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think(5, 3, 4, 10007), 5563)

    def test_2(self):
        self.assertEqual(think(4, 8, 1, 1000000), 891011)

    def test_3(self):
        self.assertEqual(think(107, 10000000000007, 1000000000000007, 998244353), 39122908)


def solve():
    l, a, b, m = read()
    result = think(l, a, b, m)
    write(result)


def read():
    return read_int(4)


def read_int(n):
    return read_type(int, n)


def read_float(n):
    return read_type(float, n)


def read_type(t, n):
    return list(map(lambda x: t(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(l, a, b, m):
    s = [a + b * i for i in range(l)]
    s_string = list(map(lambda x: str(x), s))
    num = int(''.join(s_string))
    return num % m


def write(result):
    print(result)


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    l,a,b,m=map(int,input().split())

    C=[0]*19
    for d in range(1,19):
        C[d]=(10**d-1-a)//b+1
    for d in range(18,0,-1):
        C[d]-=C[d-1]
    for d in range(1,19):
        C[d]=min(l,C[d])
        l-=C[d]

    def mul(A,B):
        from itertools import product
        C=[[0]*3 for _ in range(3)]
        for i,j,k in product(range(3),repeat=3):
            C[i][j]+=A[i][k]*B[k][j]
            C[i][j]%=m
        return C

    A=[[1,0,0],[0,1,0],[0,0,1]]
    for d in range(19):
        power=[[pow(10,d,m),1,0],[0,1,b%m],[0,0,1]]
        res=[[1,0,0],[0,1,0],[0,0,1]]
        p=C[d]
        while(p):
            if(p&1):
                res=mul(res,power)
            power=mul(power,power)
            p>>=1
        A=mul(res,A)
    print((A[0][1]*(a%m)+A[0][2])%m)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    l,a,b,m=map(int,input().split())

    C=[0]*19
    for d in range(1,19):
        C[d]=(10**d-1-a)//b+1
    for d in range(18,0,-1):
        C[d]-=C[d-1]
    for d in range(1,19):
        C[d]=min(l,C[d])
        l-=C[d]

    def mul(A,B):
        from itertools import product
        C=[[0]*3 for _ in range(3)]
        for i,j,k in product(range(3),repeat=3):
            C[i][j]+=A[i][k]*B[k][j]
            C[i][j]%=m
        return C

    A=[[1,0,0],[0,1,0],[0,0,1]]
    for d in range(19):
        power=[[pow(10,d,m),1,0],[0,1,b],[0,0,1]]
        res=[[1,0,0],[0,1,0],[0,0,1]]
        p=C[d]
        while(p):
            if(p&1):
                res=mul(res,power)
            power=mul(power,power)
            p>>=1
        A=mul(res,A)
    print((A[0][1]*a+A[0][2])%m)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    l,a,b,m=map(int,input().split())

    C=[0]*19
    for d in range(1,19):
        C[d]=(10**d-1-a)//b+1
    for d in range(18,0,-1):
        C[d]-=C[d-1]
    for d in range(1,19):
        C[d]=min(l,C[d])
        l-=C[d]

    def mul(A,B):
        from itertools import product
        C=[[0]*3 for _ in range(3)]
        for i,j,k in product(range(3),repeat=3):
            C[i][j]+=A[i][k]*B[k][j]
            C[i][j]%=m
        return C

    A=[[1,0,0],[0,1,0],[0,0,1]]
    for d in range(19):
        pow=[[(10**d)%m,1,0],[0,1,b],[0,0,1]]
        res=[[1,0,0],[0,1,0],[0,0,1]]
        p=C[d]
        while(p):
            if(p&1):
                res=mul(res,pow)
            pow=mul(pow,pow)
            p>>=1
        A=mul(res,A)
    print((A[0][1]*a+A[0][2])%m)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    l,a,b,m=map(int,input().split())

    C=[0]*19
    for d in range(1,19):
        C[d]=(10**d-1-a)//b+1
    for d in range(18,0,-1):
        C[d]-=C[d-1]
    for d in range(1,19):
        C[d]=min(l,C[d])
        l-=C[d]

    def mul(A,B):
        from itertools import product
        C=[[0]*3 for _ in range(3)]
        for i,j,k in product(range(3),repeat=3):
            C[i][j]+=A[i][k]*B[k][j]
            C[i][j]%=m
        return C

    A=[[1,0,0],[0,1,0],[0,0,1]]
    for d in range(19):
        pow=[[10**d,1,0],[0,1,b],[0,0,1]]
        res=[[1,0,0],[0,1,0],[0,0,1]]
        p=C[d]
        while(p):
            if(p&1):
                res=mul(res,pow)
            pow=mul(pow,pow)
            p>>=1
        A=mul(res,A)
    print((A[0][1]*a+A[0][2])%m)
resolve()

Submission status: Time Limit Exceeded

Solution code:
l,a,b,m=map(int,input().split())
S=''
for i in range(l):
  S+=str(a+b*i)
c=int(S)
print(c%m)

Submission status: Time Limit Exceeded

Solution code:
L, A, B, M = map(int,input().split())
s = ''
mod = M
for i in range(L):
    s += str(A+B*i)
print(int(s)%mod)

Submission status: Time Limit Exceeded

Solution code:

import math

def resolve():
    (L,A,B,M)=map(int,input().split())
    st=(L-1)*B+A
    beforemod=1
    modlist=[0,1]
    mod=0
    for i in range(19):
        modlist.append(modlist[-1]*10%M)
    for i in range(L):
        mod=((beforemod*(st%M))%M+mod)%M

        beforemod=(modlist[math.floor(math.log10(st)+1)+1]*beforemod)%M        

        st-=B

    print(mod)





resolve()

Submission status: Time Limit Exceeded

Solution code:
def digits(x):
    res=0
    while x>=1:
        x//=10
        res+=1
    return res

def power_mod(x,n,m):
    res=1
    for i in range(n):
        res=(res*x)%m
    return res

L,A,B,M=map(int,input().split())
T=0
for i in range(L):
#    print(A+B*i)
    T=((T*(power_mod(10,digits(A+B*(i)),M)))%M+(A+B*(i)))%M
#    print(T)
print(T)

Submission status: Time Limit Exceeded

Solution code:
def solve():
  l,a,b,m = (int(i) for i in input().split())
  query = ""
  for i in range(l):
    query += str(a+b*i)
  
  print(int(query)%m)
solve()

Submission status: Time Limit Exceeded

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

l-=1
num = a+b*l
l-=1

while(l>=0):
    t=len(str(num))
    num = num + (10**t)*(a+b*l)
    l-=1;

ans = num%m

print(ans)

Submission status: Time Limit Exceeded

Solution code:
L,A,B,M = map(int,input().split())
S = []
a = A
S.append(len(str(a)))
for i in range (1,L):
    a += B
    S.append(len(str(a)))
Scum = [0 for _ in range(L)]
Scum[0] = S[0]
for i in range(1,L):
    Scum[i] = Scum[i-1]+S[i]
cnt = 0
a = A
for i in range(L):
    k = Scum[-1]-Scum[i]
    cnt = (cnt+(a%M)*(10**k)%M)%M
    a += B
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#import sys
#input = sys.stdin.readline
def main():
    L, A, B, M = map( int, input().split())
    s = A
    ans = 0
    for _ in range(L):
        ans = (ans*pow(10, len( str(s)), M) + s )%M
        s += B
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

s = [str(A+B*i) for i in range(L)]
s = ''.join(s)
print(int(s) % M)

Submission status: Time Limit Exceeded

Solution code:
L,A,B,mod=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

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

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)

Submission status: Time Limit Exceeded

Solution code:
L,A,B,mod=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

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

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=0
ANS=0
for i in range(18,0,-1):
    sh,ma,kou = keta(i)
    
    if kou<=0:
        continue
    

    #print(i,sh,ma,kou)

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

print(ANS)

Submission status: Time Limit Exceeded

Solution code:
N,a,b,M = map(int, input().split())
s = a
s1 = ""
ss = []
for i in range(N):
    s1 += str(s)
    s += b
print(int(s1)%M)

Submission status: Time Limit Exceeded

Solution code:
N,a,b,M = map(int, input().split())
s = a
s1 = ""
ss = []
for i in range(N):
    ss.append(s)
    s += b
for i in ss:
    s1 = s1 + str(i)
print(int(s1)%M)

Submission status: Time Limit Exceeded

Solution code:
L,A,B,M = [int(_) for _ in input().split(" ")]
#L,A,B,M = 107 ,10000000000007 ,1000000000000007 ,998244353

BB = [0] * 64
BB[0] = 1
for i in range(1, len(BB)):
    #BB[i] = (BB[i-1] * 10)
    BB[i] = (BB[i-1] * 10) % M

_10_01 = 10
_10_02 = 100
_10_03 = 1000
_10_04 = 10000
_10_05 = 100000
_10_06 = 1000000
_10_07 = 10000000
_10_08 = 100000000
_10_09 = 1000000000
_10_10 = 10000000000
_10_11 = 100000000000
_10_12 = 1000000000000
_10_13 = 10000000000000
_10_14 = 100000000000000
_10_15 = 1000000000000000
_10_16 = 10000000000000000
_10_17 = 100000000000000000
_10_18 = 1000000000000000000

def Keta(val):
    if val < _10_09: # 1-9
        if val < _10_05: # 1-4
            if val < _10_03:
                if val < _10_01:
                    return 1
                elif val < _10_02:
                    return 2
                else:
                    return 3
            else: # 
                if val < _10_04:
                    return 4
                else:
                    return 5
        else:
            if val < _10_07:
                if  val < _10_06:
                    return 6
                else:
                    return 7
            else:
                if val < _10_08:
                    return 8
                else:
                    return 9
    else:
        if val < _10_14: # 1-4
            if val < _10_12:
                if val < _10_10:
                    return 10
                elif val < _10_11:
                    return 11
                elif val < _10_12:
                    return 12
            else: # 
                if val < _10_13:
                    return 13
                elif val < _10_14:
                    return 14
        else: 
            if val < _10_16:
                if  val < _10_15:
                    return 15
                else:
                    return 16
            else:
                if val < _10_17:
                    return 17
                elif val < _10_18:
                    return 18

start = A + L * B

k = 20
kk = 1
AA = 10**k
_sum = 0
while(start > A):
    start -= B
    t = (start * kk) % M
    if AA > start:
        k = Keta(start)
        AA = 10**k
    kk = (kk*BB[k]) % M
    _sum += t
    _sum %= M
    #print (start, k)
print (_sum % M)