AtCoder Beginner Contest 129 - Takahashi's Basics in Education and Learning

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.

Source: atcoder | Difficulty: MEDIUM_HARD


Solutions:
import sys
import itertools
import queue
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def read_values():
	return map(int, input().split())

def read_index():
	return map(lambda x: int(x) - 1, 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)
main()


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

def f(l):
	return max(0, (10 ** l - A - 1) // B + 1)

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

def p(a, n):
	r = [[0] * len(a) for i in range(len(a))]
	b = []
	for i in range(len(a)):
		r[i][i] = 1
		b.append(a[i][:])
	l = n
	while l > 0:
		if l & 1:
			r = m(b, r)
		b = m(b, b)
		l >>= 1
	return r
X = [[0, 0, 1], [0, 0, A], [0, 0, 0]]
(Y, R, Z) = (0, 1, 0)
while L:
	Y = [[1, 0, 0], [B, 1, 0], [0, 1, pow(10, R, mod)]]
	Z = min(L, f(R) - f(R - 1))
	L -= Z
	Y = p(Y, Z)
	X = m(Y, X)
	R += 1
print(X[2][2] % mod)


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
sys.setrecursionlimit(2147483647)
INF = 10 ** 20

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

def mat_mul(a, b):
	(I, J, K) = (len(a), len(b[0]), len(b))
	c = [[0] * J for _ in range(I)]
	for i in range(I):
		for j in range(J):
			for k in range(K):
				c[i][j] += a[i][k] * b[k][j]
			c[i][j] %= m
	return c

def mat_pow(x, n):
	y = [[0] * len(x) for _ in range(len(x))]
	for i in range(len(x)):
		y[i][i] = 1
	while n > 0:
		if n & 1:
			y = mat_mul(x, y)
		x = mat_mul(x, x)
		n >>= 1
	return y
(l, a, b, m) = LI()
d0 = 0
ret = [[0], [a], [b]]
for i in range(1, 19):
	if 10 ** i - 1 - a < 0:
		continue
	d1 = min((10 ** i - 1 - a) // b + 1, l)
	mat = [[10 ** i, 1, 0], [0, 1, 1], [0, 0, 1]]
	ret = mat_mul(mat_pow(mat, d1 - d0), ret)
	if d1 == l:
		break
	d0 = d1
print(ret[0][0])


(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)


(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)


def matrix_mul(A, B):
	ans = [[0] * len(B[0]) for i in range(len(A))]
	for ai in range(len(A)):
		for bj in range(len(B[0])):
			now = 0
			for same in range(len(A[0])):
				now += A[ai][same] * B[same][bj]
			ans[ai][bj] = now % mod
	return ans

def matrix_pow(A, x):
	B = [[A[i][j] for j in range(len(A[0]))] for i in range(len(A))]
	ans = [[0] * len(A[0]) for i in range(len(A))]
	for i in range(len(A)):
		ans[i][i] = 1
	while x > 0:
		if x % 2 == 1:
			ans = matrix_mul(ans, B)
		B = matrix_mul(B, B)
		x //= 2
	return ans
import sys
(L, A, C, mod) = map(int, input().split())
now = [[0, A, 1]]
LA = len(str(A))
LB = len(str(A + C * (L - 1)))
B = A + C * (L - 1)
if LA == LB:
	np = [[pow(10, LA, mod), 0, 0], [1, 1, 0], [0, C, 1]]
	k = (B - A) // C + 1
	now = matrix_mul(now, matrix_pow(np, k))
	print(now[0][0] % mod)
	sys.exit()
for i in range(LA, LB + 1):
	np = [[pow(10, i, mod), 0, 0], [1, 1, 0], [0, C, 1]]
	if i == LA:
		k = (10 ** i - 1 - A) // C + 1
		now = matrix_mul(now, matrix_pow(np, k))
	elif i == LB:
		k = (B - A) // C - (10 ** (i - 1) - 1 - A) // C
		now = matrix_mul(now, matrix_pow(np, k))
	else:
		k = (10 ** i - 1 - A) // C - (10 ** (i - 1) - 1 - A) // C
		now = matrix_mul(now, matrix_pow(np, k))
print(now[0][0] % mod)


from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

def LI():
	return list(map(int, sys.stdin.readline().split()))

def I():
	return int(sys.stdin.readline())

def LS():
	return list(map(list, sys.stdin.readline().split()))

def S():
	return list(sys.stdin.readline())[:-1]

def IR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = I()
	return l

def LIR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = LI()
	return l

def SR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = S()
	return l

def LSR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = LS()
	return l
sys.setrecursionlimit(1000000)
mod = 1000000007

def A():
	(p, q, r) = LI()
	print(p + q + r - max(p, q, r))
	return

def B():
	n = I()
	w = LI()
	ans = float('inf')
	for i in range(n):
		m = sum(w[:i])
		l = sum(w[i:])
		ans = min(ans, abs(m - l))
	print(ans)
	return

def C():
	(n, m) = LI()
	f = [1 for i in range(n + 10000)]
	for i in range(m):
		a = I()
		f[a] = 0
	dp = [0 for i in range(n + 10000)]
	dp[0] = 1
	for i in range(n):
		if f[i + 1]:
			dp[i + 1] += dp[i]
			dp[i + 1] %= mod
		if f[i + 2]:
			dp[i + 2] += dp[i]
			dp[i + 2] %= mod
	print(dp[n])
	return

def D():
	(h, w) = LI()
	s = SR(h)
	vi = [[0 for j in range(w)] for i in range(h)]
	ho = [[0 for j in range(w)] for i in range(h)]
	q = deque()
	for y in range(h):
		for x in range(w):
			if s[y][x] == '#':
				l = len(q)
				while q:
					(i, j) = q.pop()
					vi[i][j] = l
			else:
				q.append((y, x))
		l = len(q)
		while q:
			(i, j) = q.pop()
			vi[i][j] = l
	for x in range(w):
		for y in range(h):
			if s[y][x] == '#':
				l = len(q)
				while q:
					(i, j) = q.pop()
					ho[i][j] = l
			else:
				q.append((y, x))
		l = len(q)
		while q:
			(i, j) = q.pop()
			ho[i][j] = l
	ans = 0
	for y in range(h):
		for x in range(w):
			ans = max(ans, vi[y][x] + ho[y][x] - 1)
	print(ans)
	return

def E():
	b = S()
	l = len(b)
	for i in range(l):
		b[i] = int(b[i])
	dp = [[0 for j in range(2)] for i in range(1000002)]
	dp[0][0] = 1
	for i in range(l):
		for j in range(2):
			x = 1 if j else b[i]
			for d in range(x + 1):
				if d:
					dp[i + 1][j or d < b[i]] += 2 * dp[i][j]
					dp[i + 1][j or d < b[i]] %= mod
				else:
					dp[i + 1][j or d < b[i]] += dp[i][j]
					dp[i + 1][j or d < b[i]] %= mod
	ans = 0
	for j in range(2):
		ans += dp[l][j]
		ans %= mod
	print(ans)
	return

def F():

	def dot(a, b, m):
		return sum(list(map(lambda x: x[0] * x[1] % m, zip(a, b)))) % m

	def mat_mul(a, b, m):
		b_ = [[b[i][j] for i in range(len(b))] for j in range(len(b[0]))]
		return [[dot(a[i], b_[j], m) for j in range(len(b_))] for i in range(len(a))]

	def mat_pow(a, n, m):
		res = [[1 if i == j else 0 for j in range(len(a))] for i in range(len(a))]
		while n:
			if n & 1:
				res = mat_mul(res, a, m)
			n >>= 1
			a = mat_mul(a, a, m)
		return res
	(l, a, b, m) = LI()
	ans = 0
	p = 1
	s = 0
	for d in range(1, 19):
		left = max(0, -((a - p) // b))
		if left >= l:
			break
		p *= 10
		right = min(l, -((a - p) // b))
		if right <= left:
			continue
		mat = mat_pow([[p, 1, 0], [0, 1, 1], [0, 0, 1]], right - left, m)
		ans *= pow(10, d * (right - left), m)
		ans += (mat[0][1] * (a + b * left) % m + mat[0][2] * b % m) % m
		ans %= m
	print(ans)
	return
F()


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)


(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):
	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)


(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
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
(L, A, B, MOD) = map(int, read().split())

def geom_seq_sum(r, n, MOD):
	if r == 1:
		return n % MOD
	r1 = r - 1
	return (pow(r, n, r1 * MOD) - 1) // r1 % MOD

def geom_seq_sum_1(r, n, MOD):
	if r == 1:
		return n * (n - 1) // 2 % MOD
	r1 = r - 1
	x = pow(r, n, r1 * r1 * MOD)
	return (-(x - 1) // r1 + (n - 1) * x + 1) // r1 % MOD
S = 0
for d in range(1, 20):
	lower = 10 ** (d - 1)
	upper = 10 ** d - 1
	nlower = (lower - A + B - 1) // B
	nupper = (upper - A) // B
	if nlower < 0:
		nlower = 0
	if nupper >= L:
		nupper = L - 1
	if nlower > nupper:
		continue
	items = nupper - nlower + 1
	r = 10 ** d % MOD
	last = A + B * nupper
	x = last * geom_seq_sum(r, items, MOD)
	x -= B * geom_seq_sum_1(r, items, MOD)
	length = d * items
	S *= pow(10, length, MOD)
	S += x
	S %= MOD
print(S)


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


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
vec = [ModInt(0), ModInt(A), ModInt(B)]
digits = 1
while size < L:
	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])


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


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) = 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]
print(main())


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


import sys
input = sys.stdin.readline

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):
	for i in range(N):
		for j in range(N):
			A[i][j] %= Q
	return

def powOfMatrix(N, X, n, Q):
	Ret = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
	power = '{:060b}'.format(n)[::-1]
	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) = 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)
main()


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

	def identity_matrix(n):
		return [[int(i == j) for i in range(n)] for j in range(n)]

	def multiply(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):
		n = len(a)
		ret = identity_matrix(n)
		while k:
			if k & 1:
				ret = multiply(ret, a)
			a = multiply(a, a)
			k >>= 1
		return ret
	num_pow_d = [0] * (DIGIT_MAX + 1)
	for d in range(DIGIT_MAX + 1):
		if 10 ** d - 1 < A:
			continue
		num_pow_d[d] = min((10 ** d - 1 - A) // B + 1, L)
	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 sys
(L, A, B, M) = map(int, input().split())
mod = M
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
	if y == 0:
		return 1
	elif y == 1:
		return x % mod
	elif y % 2 == 0:
		return power(x, y // 2) ** 2 % mod
	else:
		return power(x, (y - 1) // 2) ** 2 * x % mod

def mul(a, b):
	return a % mod * (b % mod) % mod

def G(n, i):
	if n == 1:
		return 1
	tn = n // 2
	return (G(tn, i) * (1 + power(10, tn * i)) % mod + n % 2 * power(10, (n - 1) * i)) % mod

def G2(n, i):
	if n == 0:
		return 0
	if n == 1:
		return power(10, i) % mod
	tn = n // 2
	X = G2(tn, i)
	I = power(10, tn * i)
	Y = X * (I + 1) % mod + mul(mul(tn, I), G(tn + 1, i) - 1) % mod + mul(n % 2, mul(n, power(10, n * i)))
	return Y % mod

def f(a, b, n, i):
	if n == 0:
		return 0
	aa = mul(a, G(n, i))
	bb = mul(b, G2(n - 1, i))
	return (aa - bb) % mod
SL = A + (L - 1) * B
ts = 0
ks = [0]
for i in range(len(str(SL)) + 1):
	ks.append(max(min(10 ** (i + 1) - 1, SL) - (A - B), 0) // B - ts)
	ts += ks[-1]
ti = 0
a = SL
R = 0
for i in range(len(str(SL)) + 1, 0, -1):
	n = ks[i]
	R = (R + f(a, B, n, i) * power(10, ti)) % mod
	ti += i * n
	a -= n * B
print(R)


def dot(a, b, m):
	c = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
	for i in range(3):
		for j in range(3):
			for k in range(3):
				c[i][j] += a[i][k] * b[k][j]
				c[i][j] %= m
	return c

def powm(a, n, m):
	if n == 0:
		return [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
	for i in range(3):
		for j in range(3):
			a[i][j] %= m
	r = powm(a, n // 2, m)
	if n % 2 == 0:
		return dot(r, r, m)
	else:
		return dot(dot(r, r, m), a, m)
(L, A, B, M) = map(int, input().split())
a = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
for d in range(1, 19):
	C = min(max(0, (10 ** d - A - 1) // B + 1), L) - min(max(0, (10 ** (d - 1) - A - 1) // B + 1), L)
	a = dot(powm([[pow(10, d, M), 1, 0], [0, 1, B % M], [0, 0, 1]], C, M), a, M)
ans = (a[0][1] * A % M + a[0][2]) % M
print(ans)


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


import sys
sys.setrecursionlimit(100000000)

def mult(A, B, mod):
	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()


def mat_dot(A, B, mod):
	assert len(A[0]) == len(B), 'invalid_size'
	L = len(A)
	M = len(A[0])
	N = len(B[0])
	res = [[0] * N for _ in range(L)]
	for i in range(L):
		for j in range(N):
			a = 0
			for k in range(M):
				a = (a + A[i][k] * B[k][j]) % mod
			res[i][j] = a
	return res

def mat_pow(A, x, mod):
	N = len(A)
	res = [[0] * N for _ in range(N)]
	for i in range(N):
		res[i][i] = 1
	for i in range(x.bit_length()):
		if 2 ** i & x:
			res = mat_dot(res, A, mod)
		A = mat_dot(A, A, mod)
	return res
(L, A, B, M) = map(int, input().split())
pre = -1
S = []
for k in range(50):
	if len(str(A)) > k + 1:
		continue
	j = -((A - 10 ** (k + 1)) // B) - 1
	j = min(j, L - 1)
	j = j - pre
	pre += j
	if j:
		S.append((j, k + 1))
Ans = [[0], [A], [1]]
for (p, k) in S:
	cmat = [[pow(10, k, M), 1, 0], [0, 1, B], [0, 0, 1]]
	Ans = mat_dot(mat_pow(cmat, p, M), Ans, M)
print(Ans[0][0])


import sys
(L, A, B, M) = map(int, input().split())
mod = M
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
	if y == 0:
		return 1
	elif y == 1:
		return x % mod
	elif y % 2 == 0:
		return power(x, y // 2) ** 2 % mod
	else:
		return power(x, (y - 1) // 2) ** 2 * x % mod

def mul(a, b):
	return a % mod * (b % mod) % mod

def modinv(a):
	(b, u, v) = (mod, 1, 0)
	while b:
		t = a // b
		(a, u) = (a - t * b, u - t * v)
		(a, b, u, v) = (b, a, v, u)
	u %= mod
	return u

def div(a, b):
	return a * modinv(b) % mod

def G(n, i):
	if n == 1:
		return 1
	tn = n // 2
	return (G(tn, i) * (1 + power(10, tn * i)) % mod + n % 2 * power(10, (n - 1) * i)) % mod

def G2(n, i):
	if n == 0:
		return 0
	if n == 1:
		return power(10, i) % mod
	tn = n // 2
	X = G2(tn, i)
	I = power(10, tn * i)
	Y = (X * (I + 1) % mod + mul(mul(tn, I), G(tn + 1, i) - 1) % mod) % mod
	Y = Y + mul(n % 2, mul(n, power(10, n * i)))
	return Y % mod

def f(a, b, n, i):
	if n == 0:
		return 0
	r = power(10, i)
	P = power(r, n)
	aa = mul(a, G(n, i))
	bb2 = mul(b, div(r - n * P + (n - 1) * P * r, mul(1 - r, 1 - r)))
	bb = mul(b, G2(n - 1, i))
	return (aa - bb) % mod
sl = A + (L - 1) * B
t = 10
k = 0
ts = 0
ks = []
mk = 18
for i in range(mk):
	k = max(min(t - 1, sl) - (A - B), 0) // B - ts
	ts += k
	ks.append(k)
	t *= 10
ti = 0
ti2 = 0
b = B
R = 0
for i in range(mk):
	i = mk - i
	n = ks[i - 1]
	a = sl - ti2 * b
	if n:
		R = (R + f(a, b, n, i) * power(10, ti)) % mod
	ti += i * n
	ti2 += n
print(R)


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)


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


def rec(r, b, c, a0, n, mod):
	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) = map(int, input().split())

	def bis(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)
		ans = (ans * pow(10, d * n, M) + a) % M
	print(ans)
main()


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


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


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

def sum_ri(r, n, mod):
	if r == 1:
		return n % mod
	else:
		return (pow(r, n, mod * (r - 1)) - 1) // (r - 1) % mod

def sum_iri(r, n, mod):
	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):
	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
	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)


(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)
	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)


(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)


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


import copy
import sys
stdin = sys.stdin
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
ns = lambda : stdin.readline().rstrip()
(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
v = [0, A, B]
ra = A
while low < 1e+18:
	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)
	ra = ra + B * step
	L -= step
	low *= 10
	high *= 10
print(v[0])


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

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

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)


def mmult(A, B):
	global 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 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)
		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))


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)


(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 matmul(A, B, mod):
	res = [[0] * len(B[0]) for _ in range(len(A))]
	for i in range(len(A)):
		for (k, aik) in enumerate(A[i]):
			for (j, bkj) in enumerate(B[k]):
				res[i][j] += aik * bkj
				res[i][j] %= mod
	return res

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:
		return [[1 if i == j else 0 for j in range(len(A))] for i in range(len(A))]
(l, a, d, m) = [int(i) for i in input().split()]
r = [(10 ** (c + 1) - 1 - a) // d for c in range(18)]
MOD = m
ans = 0
flag = 0
for (c, rc) in enumerate(r):
	if rc < 0:
		continue
	C = [[pow(10, c + 1, MOD), 1, 0], [0, 1, d], [0, 0, 1]]
	if c == 0:
		C = matpow(C, rc + 1, MOD)
		ansvec = [[ans], [a], [1]]
	else:
		lc = max(r[c - 1] + 1, 0)
		C = matpow(C, min(l - 1, rc) - lc + 1, MOD)
		ansvec = [[ans], [a + d * lc], [1]]
	ans = matmul(C, ansvec, MOD)[0][0]
	if rc > l:
		break
print(ans)


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

def keta(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):
	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):
	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
	ANS = (keta_count * (ma * f(kou, 10 ** i) - B * g(kou, 10 ** i)) + ANS) % mod
	keta_count = keta_count * pow(10, kou * i, mod)
print(ANS)


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
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from functools import lru_cache
(L, A, B, MOD) = map(int, read().split())

@lru_cache(None)
def F(r, n, MOD):
	if n == 0:
		return 0
	q = n // 2
	x = F(r, q, MOD)
	x *= 1 + pow(r, q, MOD)
	x %= MOD
	if n & 1:
		x *= r
		x += 1
		x %= MOD
	return x

@lru_cache(None)
def G(r, n, MOD):
	if n == 0:
		return 0
	q = n // 2
	x = G(r, q, MOD)
	x *= 1 + pow(r, q, MOD)
	x %= MOD
	x += F(r, q, MOD) * pow(r, q, MOD) * q % MOD
	if n & 1:
		x *= r
		x += F(r, n, MOD)
		x -= 1
		x %= MOD
	return x
S = 0
for d in range(1, 20):
	lower = 10 ** (d - 1)
	upper = 10 ** d - 1
	nlower = (lower - A + B - 1) // B
	nupper = (upper - A) // B
	if nlower < 0:
		nlower = 0
	if nupper >= L:
		nupper = L - 1
	if nlower > nupper:
		continue
	items = nupper - nlower + 1
	r = 10 ** d % MOD
	last = A + B * nupper
	x = last * F(r, items, MOD)
	x -= B * G(r, items, MOD)
	length = d * items
	S *= pow(10, length, MOD)
	S += x
	S %= MOD
print(S)


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


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


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

def matmul(A, B):
	global 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, 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):
	global 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):
	global mod
	global 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
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]

def main():
	(l, a, b, md) = MI()
	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
		e = j - i
		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 main():
	import sys
	input = sys.stdin.readline
	(N, a0, d, mod) = map(int, input().split())

	def matmul(A, B):
		C = [[0] * len(B[0]) for _ in range(len(A))]
		for i in range(len(A)):
			for j in range(len(B[0])):
				for k in range(len(B)):
					C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod
		return C

	def matpow(A, p):
		n = len(A)
		B = [[0] * n for _ in range(n)]
		for i in range(n):
			B[i][i] = 1
		while p > 0:
			if p & 1:
				B = matmul(B, A)
			A = matmul(A, A)
			p >>= 1
		return B
	ans = [[a0 % mod], [a0 % mod], [d % mod]]
	ok_prev = 0
	for i in range(len(str(a0)), 20):
		ok = N
		ng = -1
		mid = (ok + ng) // 2
		while ok - ng > 1:
			if len(str(a0 + d * mid)) >= i + 1:
				ok = mid
			else:
				ng = mid
			mid = (ok + ng) // 2
		mat = [[10 ** i % mod, 1, 1], [0, 1, 1], [0, 0, 1]]
		ans = matmul(matpow(mat, ok - ok_prev - 1), ans)
		ok_prev = ok - 1
		if ok == N:
			break
	print(ans[0][0])
main()


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 math
(L, A, D, mod) = map(int, input().split())
que = []
ans = 0
for i in range(1, 22):
	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):
	if N == 0:
		return 1
	if N == 1:
		return (X + 1) % mod
	elif 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):
	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):
	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)


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

def partsum(a, b, l, n):
	doublingconst = [0 for i in range(0, 60)]
	doublingconst[0] = 1
	doublingline = [0 for i in range(0, 60)]
	doublingline[0] = 0
	for i in range(1, 60):
		doublingconst[i] = (pow(10, l * 2 ** (i - 1), M) + 1) * doublingconst[i - 1] % M
		doublingline[i] = ((pow(10, l * 2 ** (i - 1), M) + 1) * doublingline[i - 1] + pow(2, i - 1, M) * pow(10, l * 2 ** (i - 1), M) * doublingconst[i - 1]) % M
	ansconst = 0
	chousei = 0
	for i in range(0, 60):
		if n >> i & 1 == 1:
			ansconst += doublingconst[i] * pow(10, chousei * l, M)
			ansconst %= M
			chousei += 2 ** i
	ansline = 0
	chousei = 0
	for i in range(0, 60):
		if n >> i & 1 == 1:
			ansline += (doublingline[i] + chousei * doublingconst[i]) * pow(10, chousei * l, M)
			ansline %= M
			chousei += 2 ** i
	return ansline * a + ansconst * b
start = len(str(A))
end = len(str(B * L + A - B))
part = []
for i in range(start - 1, end):
	l = 1 + (10 ** i - A - 1) // B
	r = (10 ** (i + 1) - A - 1) // B
	l = max(0, l)
	r = min(L - 1, r)
	part.append([i + 1, l, r])
part.sort(reverse=True)
ans = 0
chousei = 0
for i in range(0, len(part)):
	(length, l, r) = part[i]
	const = B * r + A
	line = B
	ans += partsum(-line, const, length, r - l + 1) * pow(10, chousei, M) % M
	ans %= M
	chousei += length * (r - l + 1)
print(ans)


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)


import sys
sys.setrecursionlimit(10 ** 7)
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right
from collections import deque, defaultdict
from collections import Counter
from itertools import accumulate, combinations, permutations
from heapq import heapify, heappop, heappush
from functools import reduce, lru_cache
from decimal import Decimal

def input():
	x = sys.stdin.readline()
	return x[:-1] if x[-1] == '\n' else x

def printe(*x):
	print('## ', *x, file=sys.stderr)

def printl(li):
	_ = print(*li, sep='\n') if li else None

def argsort(s, return_sorted=False):
	inds = sorted(range(len(s)), key=lambda k: s[k])
	if return_sorted:
		return (inds, [s[i] for i in inds])
	return inds

def alp2num(c, cap=False):
	return ord(c) - 97 if not cap else ord(c) - 65

def num2alp(i, cap=False):
	return chr(i + 97) if not cap else chr(i + 65)

def matmat(A, B, mod):
	(K, N, M) = (len(B), len(A), len(B[0]))
	return [[sum([A[i][k] * B[k][j] for k in range(K)]) % mod for j in range(M)] for i in range(N)]

def matvec(M, v):
	(N, size) = (len(v), len(M))
	return [sum([M[i][j] * v[j] for j in range(N)]) for i in range(size)]

def T(M):
	(n, m) = (len(M), len(M[0]))
	return [[M[j][i] for j in range(n)] for i in range(m)]

def main():
	(L, A, B, M) = map(int, input().split())
	mod = M
	ans = 0
	cur = 0
	a10 = 1
	cs = A
	for alp in range(18):
		l = a10 - A - 1
		r = a10 * 10 - A - 1
		a10 *= 10
		if r < 0:
			continue
		if l < 0:
			lb = 0
		else:
			lb = l // B + 1
		rb = r // B + 1
		rrb = min(L, rb)
		n = rrb - lb
		mat = [[0] * 3 for _ in range(3)]
		mat[0][0] = pow(10, alp + 1, mod)
		mat[0][1] = 1
		mat[1][1] = 1
		mat[1][2] = B % mod
		mat[2][2] = 1
		v = [ans, cs, 1]
		tot = [[0] * 3 for _ in range(3)]
		for i in range(3):
			tot[i][i] = 1
		for j in range(n.bit_length()):
			if n >> j & 1:
				tot = matmat(mat, tot, M)
			mat = matmat(mat, mat, M)
		x = matvec(tot, v)
		ans = x[0] % mod
		cs = x[1] % mod
		if rb > L:
			break
	print(ans)
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])


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)
	if C[d] > L:
		break
print(s[0])


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):
	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) = map(int, input().split())
	global MOD
	MOD = m
	x = [[0], [a], [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)
main()


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


import numpy as np
(l, a, b, m) = list(map(int, input().split()))
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] = max((ten_pow[i] - 1 - a) // b, 0)
d[-1] = l - 1
cd = [d[i + 1] - d[i] for i in range(len(d) - 1)]
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
	k = cd[i]
	while k > 0:
		if k & 1:
			y = np.dot(x, y) % m
		x = np.dot(x, x) % m
		k = k >> 1
ans = y[0] % m
print(ans)


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)


def S1(r, T, M):
	if r == 1:
		return T % M
	x = pow(r, T, M * (r - 1)) - 1
	return x // (r - 1) % M

def S2(r, T, M):
	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 sys
sys.setrecursionlimit(pow(10, 6))
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()


(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 f_takahashi_basics_in_education_and_learning(L, A, B, M, DIGIT_MAX=18):
	import numpy

	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
	num_pow_d = [0] * (DIGIT_MAX + 1)
	for d in range(DIGIT_MAX + 1):
		if 10 ** d - 1 >= A:
			num_pow_d[d] = min((10 ** d - 1 - A) // B + 1, L)
	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))


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

def mat_pow(x, n):
	y = [[0] * 3 for _ in range(3)]
	for i in range(3):
		y[i][i] = 1
	while n > 0:
		if n & 1:
			y = mat_mul(x, y)
		x = mat_mul(x, x)
		n >>= 1
	return y

def mat_mul(a, b):
	(I, J, K) = (len(a), len(b[0]), len(b))
	c = [[0] * J for _ in range(I)]
	for i in range(I):
		for j in range(J):
			for k in range(K):
				c[i][j] += a[i][k] * b[k][j]
			c[i][j] %= M
	return c
n0 = -(-(10 ** 0 - A) // B)
n1 = -(-(10 ** 1 - A) // B)
ret = [[0], [A], [1]]
for d in range(1, 19):
	mat = [[10 ** d, 1, 0], [0, 1, B], [0, 0, 1]]
	if n0 < 0 and 0 < n1:
		n0 = 0
	if 0 <= n0 < n1:
		ret = mat_mul(mat_pow(mat, n1 - n0), ret)
	(n0, n1) = (n1, min(-(-(10 ** (d + 1) - A) // B), L))
print(ret[0][0])


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


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

def imat(n):
	ret = [[1 if i == j else 0 for j in range(n)] for i in range(n)]
	return ret

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)
dlist = [slist[0]]
for d in range(1, 18):
	dlist.append(slist[d] - slist[d - 1])
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
vec = [[0], [A], [1]]
vec = prod_mat(mat, vec)
print(vec[0][0] % MOD)


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()