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: Runtime Error

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] = 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])

Submission status: Runtime Error

Solution code:
import numpy

def power(mat:numpy.matrix, n, mod):
    ret = mat
    n -= 1
    while n > 0:
        if n % 2 == 1:
            ret = ret @ mat % mod
        mat = mat @ mat % mod
        n //= 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 = 10
for i in range(1, digit_n + 1):
    x = min(d - 1, s_foot) - a
    if x < 0:
        continue
    n = x // b
    count_digit_n[i] = n + 1
    d *= 10

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

d = 10
i = 0
x = numpy.matrix([[0], [a], [1]])

for n in count_digit_n:
    if n == 0:
        continue
    mat = numpy.matrix([[d, 1, 0], [0, 1, b], [0, 0, 1]])
    x = power(mat, n, m) @ x % m
    d = d * 10 % m
print(x[0][0][0])

Submission status: Runtime Error

Solution code:
n, a, b, MOD = map(int, input().split())


def mult(A, B, N):
    C = [[0] * n for _ in range(n)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                C[i][j] += A[i][k] * B[k][j]
            C[i][j] %= MOD
    return C


def mat_power(A, N, n):
    if n == 0:
        res = [[0] * N for _ in range(N)]
        for i in range(N):
            res[i][i] = 1
        return res
    X = mat_power(A, N, n // 2)
    X = mult(X, X, N)
    return mult(A, X, N) if n & 1 else X


li = [0]
t = 1
while li[-1] < n:
    p = pow(10, t)
    l, r = li[-1] - 1, n
    while r - l > 1:
        m = (l + r) // 2
        if a + b * m < p:
            l = m
        else:
            r = m
    li.append(r)
    t += 1
ans = 0
for i in range(len(li) - 1):
    p = pow(10, i + 1)
    t = li[i + 1] - li[i]
    am = [[p, 1, 0], [0, 1, 1], [0, 0, 1]]
    mat = mat_power(am, 3, t)
    ans *= pow(10, t * (i + 1), MOD)
    ans += mat[0][1] * ((a + b * li[i])) + mat[0][2] * b
    ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
l, a, b, m = 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 = [1]
while ten_pow[-1] <= s_max:
    ten_pow.append(ten_pow[-1] * 10)
D_MAX = len(ten_pow)
d = [0] * D_MAX
for i in range(D_MAX):
    if ten_pow[i] >= a:
        d[i] = (ten_pow[i] - a) // b
        if (ten_pow[i] - a) % b == 0:
            d[i] -= 1
d[-1] = l - 1
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], 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 = (x @ y) % m
            # print('y', y)
        x = (x @ x) % m
        k = k >> 1

ans = y[0]
print(ans)

Submission status: Runtime Error

Solution code:
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")

    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 = cur @ mat
                cur = np.mod(cur, m)
            mat = mat @ mat
            mat = np.mod(mat, m)
        res = res @ cur
        res = np.mod(res, m)

    print(res[0])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from numpy.linalg import matrix_power

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 = ans @ matrix_power(T, cnt)

    size += cnt
    if size >= L:
        break

print(ans[0])

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
def sc(s):
    b = None
    nc = 0
    kk = [0]*len(s)
    for i, c in enumerate(s):
        if c == ".":
            if c == b:
                nc += 1
            else:
                si = i
        else:
            if b == ".":
                for j in range(si, i):
                    kk[j] = i - si
            nc = 0
        b = c
    return kk
d = []
d2 = []
d3 = []
for h in range(H):
    s = input().strip() + "#"
    d.append(s)
    d2.append(sc(s))

for i in range(W):
    s = ""
    for j in range(H):
        s += d[j][i]
    s += "#"
    d3.append(sc(s))
r = 0
for i in range(H):
    for j in range(W):
        r = max(r, d2[i][j] + d3[j][i]-1)
print(r)

Submission status: Runtime Error

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)
    wrire(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: Runtime Error

Solution code:
import sys
from io import StringIO
import unittest
import math
class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """5 3 4 10007"""
        output = """5563"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """4 8 1 1000000"""
        output = """891011"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """107 10000000000007 1000000000000007 998244353"""
        output = """39122908"""
        self.assertIO(input, output)
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)





if __name__ == "__main__":
    rseolve()

Submission status: Runtime Error

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

print(int(string) % M)

Submission status: Runtime Error

Solution code:
l,a,b,m = list(map,(int,split(" ")))
l = []
buf = a
for _ in range(l+1):
  l.append(buf)
  buf += b
num = int("".join(list(map(str,l))))
print(num%m)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import numpy as np
L,A,B,M=(int(i) for i in input().split())
array=np.arange(A,A+B*L-1,B)
result=""
for i in range(L):
    result+=str(array[i])
print(int(result)%M)

Submission status: Runtime Error

Solution code:
L,A,B,M=(int(i) for i in input().split())
import numpy as np
array=np.arange(A,A+B*L-1,B)
result=""
for i in range(L):
    result+=str(array[i])
print(int(result)%M)

Submission status: Runtime Error

Solution code:
def mult(A, B, mod): #行列A, Bの内積を求める。
    D = [[0, 0, 0] for i in range(3)]
    D[0][0] = (A[0][0] * B[0][0]) % mod
    D[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % mod
    D[1][1] = 1
    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
    D[2][2] = 1
    return D


def Cpow(C, n, mod):
    if n == 1: return C
    else:
        D = mult(C, 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 nd == ne and ne == L - 1: break
        elif nd == ne: continue
        C = [[pow(10, d, M), 0, 0], [1, 1, 0], [0, b % M, 1]]
        D = Cpow(C, ne - nd, M)
        X = str((int(X) * D[0][0] + D[1][0] * s + D[2][0]) % M)
        s += D[2][1]
        nd = ne
    print(X)
    return

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
from multiprocessing import Pool

def calc_rem(arg):
    A, B, x = arg
    return (A + B*x)

def main():

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

    rems = []


    with Pool(processes=5) as p:
        rems = p.map(calc_rem, zip([A] * L, [B] * L, range(L)))

    rem = 0
    for i in range(L):
        si = rems[i]
        ndigs = len(str(si))
        remsi = si % M
        rem = ((rem * (10 ** ndigs)) + remsi) % M
    print(rem)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from multiprocessing import Pool
L, A, B, M = map(int, input().split(" "))

rems = []

def calc_rem(x):
    return (A + B*x)

with Pool(processes=5) as p:
    rems = p.map(calc_rem, range(L))

rem = 0
for i in range(L):
    si = rems[i]
    print("Test")
    exit(0)
    ndigs = len(str(si))
    remsi = si % M
    rem = ((rem * (10 ** ndigs)) + remsi) % M
print(rem)

Submission status: Runtime Error

Solution code:
from multiprocessing import Pool
L, A, B, M = map(int, input().split(" "))

rems = []

def calc_rem(x):
    return (A + B*x)

with Pool(processes=5) as p:
    rems = p.map(calc_rem, range(L))

rem = 0
for i in range(L):
    si = rems[i]
    ndigs = len(str(si))
    remsi = si % M
    rem = ((rem * (10 ** ndigs)) + remsi) % M
print(rem)

Submission status: Runtime Error

Solution code:
from multiprocessing import Pool
L, A, B, M = map(int, input().split(" "))

rems = []

def calc_rem(x):
    return (A + B*x)

with Pool(5) as p:
    rems = p.map(calc_rem, range(L))

rem = 0
for i in range(L):
    si = rems[i]
    ndigs = len(str(si))
    remsi = si % M
    rem = ((rem * (10 ** ndigs)) + remsi) % M
print(rem)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<cmath>
using namespace std;

int ndigs(long long n) {
  int nd = 0;
  while(n > 0) {
    nd += 1;
    n /= 10;
  }

  return nd;
}

int main() {
  long long L, A, B, M;
  cin >> L >> A >> B >> M;

  long long rem = 0;
  long long remA = A % M;
  long long remB = B % M;
  long long si, nd, p, a;
  for(long long i = 0; i < L; i++) {
    si = (remA + (i * remB)) % M;
    nd = ndigs(A + i*B);
    p = powl(10, nd);
    a = (rem * (p % M)) % M;
    rem = (a + si) % M;
  }

  cout << rem;
}

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<cmath>
using namespace std;

int ndigs(long long n) {
  int nd = 0;
  while(n > 0) {
    nd += 1;
    n /= 10;
  }

  return nd;
}

int main() {
  long long L, A, B, M;
  cin >> L >> A >> B >> M;

  long long rem = 0;
  long long remA = A % M;
  long long remB = B % M;
  for(long long i = 0; i < L; i++) {
    long long si = (remA + (i * remB)) % M;
    long long nd = ndigs(A + i*B);
    long long p = powl(10, nd);
    long long a = (rem * (p % M)) % M;
    rem = (a + si) % M;
  }

  cout << rem;
}


/*

a%b * c%b = (a*c) % b % b

9%7 * 11%7 = (99%7)%7 = 1
2 * 4 % 7 = 8 % 7 = 1

*/

Submission status: Runtime Error

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

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

n = ""
for i in range(L):
  n.join(str(si(i)))
n = int(n)

print(n % M)

Submission status: Runtime Error

Solution code:
#memo
exit()

import math

def nasu(A, B, L, D, M, T):
  ans = nasuA(A, B, L, D, M, T)
  ans += nasuB(B, L, D, M, T)
  return ans % M

def nasuA(A, B, L, D, M, T):
  ans = A % M
  ans += powA(A, B, L, D, M, T) % M
  return ans % M

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



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)
  print(n)
  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 ** 18:
  T.append(T[-1] * 2)

print(D)
ans = 0
for i in range(20):
  a = D[i][0]
  l = D[i][1]
  if l == 0:
    continue
  ans = (ans + nasu(a, B, l, pow(10, i), M, T)) % M
  
print(ans)

Submission status: Runtime Error

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

# first i such that A + i*B has d digits.
# A + i*B >= 10^d
# i*B >= 10^d - A
# i >= 
# i = (10^d - A + (B-1))/B

def get_indices(d):
	i_start = (10**d - A + (B-1)) / B
	i_end = (10**(d+1) - A + (B-1)) / B
	i_start = max(0, i_start)
	i_end = max(0, i_end)
	i_start = min(L, i_start)
	i_end = min(L, i_end)
	return (d+1, i_start, i_end)
	
index_pairs = [get_indices(n) for n in xrange(0, 19)]

def get_chunk_value(num_digs, i_start, i_end):
	if i_start == i_end:
		return (0, 0)
	
	a = A + B*(i_end - 1)
	d = -B
	n = i_end - i_start
	r = 10 ** num_digs
	
	Mt = M*((1-r)**2)
	
	numerator = (1-r)*(a - (a + n*d)*pow(r, n, Mt)) + d*r*(1 - pow(r, n, Mt))
	numerator %= Mt
	assert numerator % (1-r)**2 == 0
	return (num_digs*(i_end-i_start), numerator/(1-r)**2)
	
	

# print index_pairs
chunk_values = [get_chunk_value(n, i_start, i_end) for n, i_start, i_end 
													in index_pairs]
# print chunk_values

ans = 0
digits_offset = 0
for num_digs, value in reversed(chunk_values):
	ans += value * pow(10, digits_offset)
	digits_offset += num_digs
	
ans %= M
print ans

Submission status: Runtime Error

Solution code:
L,A,B,M=map(int,input().split())
mod=M
C=A+B*(L-1)
ans=0
def S(x,l,r,mod):
    return ((pow(x,r+1)-pow(x,l))//(x-1))%mod
def Sa(x,l,r,mod):
    return (pow(x,r+1)-pow(x,l))//(x-1)
def SS(x,l,r,mod):
    if l==r:
        return x
    return ((r*pow(x,r+1)-l*pow(x,l)-Sa(x,l+1,r,mod))//(x-1))%mod
now=0
Sx=1
while True:
    if C<A:
        break
    if len(str(C))==1:
        r=C//B
    else:
        r=(C-pow(10,len(str(C))-1))//B
    if r==0:
        ans=(ans+C*Sx)%mod
        Sx=Sx*pow(10,len(str(C)),mod)%mod
        C-=B
        now+=1
    else:
        if now+r>=L:
            r=L-now-1
        x=pow(10,len(str(C)),mod)
        y0=(C*(S(x,1,r,mod)+1))%mod
        y1=(-1*B*SS(x,1,r,mod))%mod
        y=(Sx*(y0+y1))%mod
        ans=(ans+y)%mod
    Sx=(Sx*pow(10,(r+1)*len(str(C)),mod))%mod
    C-=(r+1)*B
    now+=r+1
print(ans)

Submission status: Runtime Error

Solution code:
L,A,B,M=map(int,input().split())
mod=M
C=A+B*(L-1)
ans=0
def S(x,l,r,mod):
    if l==r:
        return pow(x,l,mod)
    rev=pow(x-1,mod-2,mod)
    return (pow(x,r+1,mod)-pow(x,l,mod))*rev%mod
def SS(x,l,r,mod):
    if l==r:
        return l*pow(x,l,mod)%mod
    rev=pow(x-1,mod-2,mod)
    return rev*(r*pow(x,r+1,mod)-l*pow(x,l,mod)-S(x,l+1,r,mod))%mod
now=0
Sx=1
times=len(str(C))
for dL in range(times,0,-1):
    if len(str(C))==1:
        r=C//B
    else:
        r=(C%pow(10,len(str(C))-1))//B
    if r==0:
        ans=(ans+C)%mod
    else:
        if now+r>=L:
            r=L-now-1
        x=pow(10,len(str(C)),mod)
        y=Sx*(C*(S(x,1,r,mod)+1)-B*SS(x,1,r,mod))%mod
        ans=(ans+y)%mod
    Sx=Sx*pow(10,(r+1)*len(str(C)),mod)%mod
    C-=(r+1)*B
    now+=r+1
print(ans)

Submission status: Runtime Error

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

nums = [a]*l
num = []
for i in range(l):
    num.append(str(nums.pop() + i * b))
    
print(int(''.join(num))%m)

Submission status: Runtime Error

Solution code:
n, a, b, mod = map(int, input().split())

sum = 0
initial = len(str(a))
last = len(str(a + b * (n - 1)))

dcnt = dict()
for i in range(initial, last + 1):
    l = 0
    r = n
    th = pow(10, i)
    while (r - l > 1):
        k = (l + r) // 2
        s = a + b * k
        if (s < th):
            l = k
        else:
            r = k
    dcnt[i] = l + 1 - sum
    sum = l + 1

a = (a + b * (n - 1) % mod) % mod
b = (mod - (b % mod)) % mod

ret = 0
p = 0
cc = 0

for d in range(last, initial - 1, -1):
    cnt = dcnt[d]
    if (d == last):
        cnt = cnt + 1
    else:
        if (d == initial):
            cnt = cnt - 1

    w = pow(10, p, mod)
    r = pow(10, d, mod)

    m = mod * (r - 1)

    t = 0 if r == 0 else cnt if r == 1 else (pow(r, cnt, m) + m - 1) % m // (r - 1)
    q = w * t % mod

    t = 0 if r == 1 else (pow(r, cnt, m * (r - 1)) + m * (r - 1) - 1) % (m * (r - 1)) // (r - 1)

    u = ((cnt - 1) % m * pow(r, cnt, m) % m + 1 + m - t) % m
    v = 0 if r == 0 else cnt * (cnt - 1) // 2 if r == 1 else u % m // (r - 1)

    ret = (ret + (a + b * cc % mod) % mod * q % mod + v * w % mod * b % mod) % mod

    p = p + d * (cnt - 1) + d - 1

    cc = cc + cnt

print(ret)

Submission status: Runtime Error

Solution code:
def f_takahashi_basics_in_education_and_learning(L, A, B, M, DIGIT_MAX=18):
    import numpy
    # 数列に対して、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 = 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), 0, 0], [1, 1, 0], [0, B, 1]], dtype='object')
        array = numpy.dot(array, numpy.linalg.matrix_power(matrix, c_d))
        array %= M
    return array[0]

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

Submission status: Runtime Error

Solution code:
import numpy as np
from math import ceil
def powm(a,n,m):
    if n == 0:
        return np.eye(len(a))
    if n%2==0:
        return np.dot(powm(a,n//2,m),powm(a,n//2,m))%m
    else:
        return np.dot(np.dot(powm(a,n//2,m),powm(a,n//2,m)),a)%m

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

C = [0]*18
d = 0
while True:
    C[d] = max(0,min(ceil((10**d-A)/B),L))
    if C[d] == L:
        break
    d += 1

for d in range(17,-1,-1):
    if C[d] != 0:
        C[d] -= C[d-1]

a = np.eye(3)
for d in range(1,18):
    a = np.dot(powm(np.array([[10**d%M,1,0],[0,1,B],[0,0,1]]),C[d],M),a)

ans = int(np.dot(a,np.array([0,A,1]))[0])%M

print(ans)

Submission status: Runtime Error

Solution code:
def d_lamp(H, W, Grid):
    num_left = [[0] * W for _ in range(H)]
    num_right = [[0] * W for _ in range(H)]
    num_down = [[0] * W for _ in range(H)]
    num_up = [[0] * W for _ in range(H)]

    for row in range(H):
        for col in range(W):
            if Grid[row][col] == '.':
                num_left[row][col] = 1 if col == 0 else (num_left[row][col - 1] + 1)

    for row in range(H):
        for col in range(W - 1, -1, -1):
            if Grid[row][col] == '.':
                num_right[row][col] = 1 if col == W - 1 else (num_right[row][col + 1] + 1)

    for col in range(W):
        for row in range(H):
            if Grid[row][col] == '.':
                num_up[row][col] = 1 if row == 0 else (num_up[row - 1][col] + 1)

    for col in range(W):
        for row in range(H - 1, -1, -1):
            if Grid[row][col] == '.':
                num_down[row][col] = 1 if row == H - 1 else (num_down[row + 1][col] + 1)

    ans = max(num_left[row][col] + num_right[row][col] + num_up[row][col]
              + num_down[row][col] - 3 for row in range(H) for col in range(W))
    return ans

H, W = [int(i) for i in input().split()]
Grid = [input() for _ in range(H)]
print(d_lamp(H, W, Grid))

Submission status: Runtime Error

Solution code:
L, A, B, M = 1, 1, 1, 1


def a(idx):
  return A + B * idx


hosei = 1
last = 1


def f(keta):
  R = 10 ** (keta - 1)
  t = 0
  global last
  if a(last) >= R:
    cant = -1
    can = L - 1
    while can - cant > 1:
      m = (can + cant) // 2
      if a(m) >= R:
        can = m
      else:
        cant = m
    first = can
    n = last - first + 1
    aa = a(last) % M
    r = R * 10 % M
    t1 = (r ** n - r) // (r - 1) * B
    t2 = (aa - (n - 1) * B) * r ** n
    t = aa - t1 - t2
    t //= 1 - r
    global hosei
    t %= M
    t *= hosei
    t %= M
    hosei = hosei * 10 ** (keta * n)
    hosei %= M
    last = first - 1
  return t


def main():
  global L
  global A
  global B
  global M
  L, A, B, M = map(int, input().split())
  global last
  last = L - 1
  ans = 0
  ans += f(18)
  ans += f(17)
  ans += f(16)
  ans += f(15)
  ans += f(14)
  ans += f(13)
  ans += f(12)
  ans += f(11)
  ans += f(10)
  ans += f(9)
  ans += f(8)
  ans += f(7)
  ans += f(6)
  ans += f(5)
  ans += f(4)
  ans += f(3)
  ans += f(2)
  ans += f(1)
  ans %= M
  print(ans)


main()

Submission status: Runtime Error

Solution code:
L, A, B, M = 1, 1, 1, 1


def a(idx):
  return A + B * idx


hosei = 1
last = 1


def f(keta):
  R = 10 ** (keta - 1)
  t = 0
  global last
  if a(last) >= R:
    cant = -1
    can = L - 1
    while can - cant > 1:
      m = (can + cant) // 2
      if a(m) >= R:
        can = m
      else:
        cant = m
    first = can
    n = last - first + 1
    aa = a(last) % M
    r = R * 10 % M
    t1 = (r ** n - r) // (r - 1) * B
    t2 = (aa - (n - 1) * B) * r ** n
    t = aa - t1 - t2
    t //= 1 - r
    global hosei
    t *= hosei
    t %= M
    hosei = hosei * 10 ** (keta * n)
    last = first - 1
  return t

def main():
  global L
  global A
  global B
  global M
  L, A, B, M = map(int, input().split())
  global last
  last = L - 1
  int
  ans = 0
  ans += f(18)
  ans += f(17)
  ans += f(16)
  ans += f(15)
  ans += f(14)
  ans += f(13)
  ans += f(12)
  ans += f(11)
  ans += f(10)
  ans += f(9)
  ans += f(8)
  ans += f(7)
  ans += f(6)
  ans += f(5)
  ans += f(4)
  ans += f(3)
  ans += f(2)
  ans += f(1)
  ans %= M
  print(ans)

main()

Submission status: Runtime Error

Solution code:
inputs = [int(s) for s in input().split()]
l = inputs[0]
a = inputs[1]
b = inputs[2]
m = inputs[3]

s = [0]*l
result = 0

for i in range(l):
    s[i] = a + b*i

k = 0
mk = len(str(m))
for i in range(l-1, -1, -1):
    result = (result + s[i] * (10 ** k)) % m
    k = k + len(str(s[i]))

print(result)

Submission status: Runtime Error

Solution code:
import numpy as np
T = input()
data = T.split()
L, A, B, M = list(map(int, data))
END = A + B * L
ans_list = np.arange(A, END, B)
tmp = 0
for i in range(len(ans_list)):
    tmp = int(str(tmp) + str(ans_list[i])) % M
print(tmp)