Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

INF = 10**9
H, W = map(int, input().split())
A = [list(input()) for h in range(H)]
# (0, 0), (0, W-1), (H-1, 0), (H-1, W-1)
ans = [[INF for w in range(W)] for h in range(H)]
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            ans[h][w] = 0
        tmp = ans[h][w]+1
        if h < H-1:
            ans[h+1][w] = min(tmp, ans[h+1][w])
        if w < W-1:
            ans[h][w+1] = min(tmp, ans[h][w+1])
for h in range(H-1, -1, -1):
    for w in range(W-1, -1, -1):
        tmp = ans[h][w]+1
        if h > 0:
            ans[h-1][w] = min(tmp, ans[h-1][w])
        if w > 0:
            ans[h][w-1] = min(tmp, ans[h][w-1])
# print(ans)
print(max([w for h in ans for w in h]))


### FIXED CODE ###

INF = 10**9
H, W = map(int, input().split())
A = [list(input()) for h in range(H)]
# (0, 0), (0, W-1), (H-1, 0), (H-1, W-1)
ans = [[INF for w in range(W)] for h in range(H)]
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            ans[h][w] = 0
        tmp = ans[h][w]+1
        if h < H-1:
            ans[h+1][w] = min(tmp, ans[h+1][w])
        if w < W-1:
            ans[h][w+1] = min(tmp, ans[h][w+1])
for h in range(H-1, -1, -1):
    for w in range(W-1, -1, -1):
        tmp = ans[h][w]+1
        if h > 0:
            ans[h-1][w] = min(tmp, ans[h-1][w])
        if w > 0:
            ans[h][w-1] = min(tmp, ans[h][w-1])
# print(ans)
print(max([w for h in ans for w in h]))
### BUGGY CODE ###

s = []
N = int(input())
for n in range(N):
    s.append(input())

count = 0
for i in range(N):
    for j in range(i+1, N):
        if sorted(s[i]) == sorted(s[j]):
            count += 1
print(count)


### FIXED CODE ###

ss = []
N = int(input())
for n in range(N):
    s = sorted(input())
    ss.append(s)

ss = sorted(ss)

total = 0
count = 0
for n in range(N):
    if n==0:
        continue
    # print("ss["+str(n-1)+"]="+str(ss[n-1]))
    # print("ss["+str(n)+"]="+str(ss[n]))
    if ss[n-1]==ss[n]:
        count += 1
    else:
        total += int(count*(count+1)/2)
        count = 0
    # print("===")
total += int(count*(count+1)/2)
count = 0

print(int(total))
### BUGGY CODE ###

import fractions
nm=raw_input()
nm=nm.split()
n=eval(nm[0])
m=eval(nm[1])
s=raw_input()
t=raw_input()

gg=fractions.gcd(n,m)
ll=n/gg*m
aa=m/gg
bb=n/gg
result = ll
for i in xrange(ll) :
    if not (i % aa):
        tmp1=i/aa
        if not(i % bb) :
            tmp2=i/bb
            if s[tmp1] != t[tmp2] :
                result= -1
print result


### FIXED CODE ###

import fractions
nm=raw_input()
nm=nm.split()
n=eval(nm[0])
m=eval(nm[1])
s=raw_input()
t=raw_input()

gg=fractions.gcd(n,m)
ll=n/gg*m
result = ll
for i in xrange(n):
    if not (i*m) % n :
            tmp=i*m/n
            if s[i] != t[tmp] :
                result= -1
print result
### BUGGY CODE ###

N,M=map(int,input().split())
ps=[list(input().split()) for _ in range(M)]

a=[]
b=[]
count=0
count_1=0

for i in range(M):
    if ps[i][1]=="AC" and ps[i][0] not in a:
        a.append(ps[i][0])

for j in range(M):
    if ps[j][0] in b and ps[j][0] not in a:
        pass
    elif ps[j][0] not in b:
        if ps[j][0] in a and ps[j][1]=="WA":
            count+=1
        elif ps[j][0] in a and ps[j][1]=="AC":
            b.append(ps[j][0])

print(len(a),count)


### FIXED CODE ###

N,M=map(int,input().split())

AC=[0]*N
WA=[0]*N
ac=0
wa=0

for i in range(M):
    p,s=map(str,input().split())
    P=int(p)
    if s=="AC":
        if AC[P-1]!=P:
            AC[P-1]+=P
            ac+=1
            wa+=WA[P-1]
    else:
        if AC[P-1]!=P:
            WA[P-1]+=1

print(ac,wa)
### BUGGY CODE ###

n = int(input())
list_A = input().split()
q = int(input())
SUM = sum(map(int, list_A))
for i in range(q):
  b, c = input().split()
  dif = 0
  cnt = 0
  if b in list_A:
    flag = True
    while flag:
      try:
        Index = list_A.index(b)
        list_A[Index] = c
        cnt += 1
      except ValueError:
        flag = False
  else:
    pass
  dif = cnt*(int(c) - int(b))
  SUM += dif
  print(SUM)

### FIXED CODE ###

import sys
from collections import Counter
n = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
q = int(sys.stdin.readline().rstrip())
count_dic = Counter(A)
SUM = sum(A)
for i in range(q):
  b, c = map(int, input().split())
  SUM += count_dic[b]*(c - b)
  count_dic[c] += count_dic[b]
  count_dic[b] = 0
  print(SUM)
### BUGGY CODE ###

# ABC104-C

D,G=map(int,input().split()) 
box=[] 
for i in range(D): 
    box.append(list(map(int,input().split()))) 
box.insert(0,[0,0]) #数を１番目に合わせるため 
info=[[0,0] for i in range(2**D)] #各全完の組での点数、解いた問題数の記憶

for i in range(2**D): #全完したものをinfoに追加
    for j in range(1,D+1): #100j点の問題は全完するか 
        if (i>>(j-1))&1: 
            info[i][0]+=box[j][1]+j*100*box[j][0] 
            info[i][1]+=box[j][0] 

for i in range(2**D):
    score=G-info[i][0]
    if score<=0:
        continue
    else:
        n=D
        while score>0:
            if (i>>(n-1))&1:
                continue
            else:
                for j in range(1,box[n][0]+1):
                    score -= 100*n
                    info[i][1]+=1 #解いた数を増やす
                    if j==box[n][0]: #ボーナス点追加
                        score-=box[n][1]
                    if  score<=0:
                        break
            n-=1
            
l=len(info)
for i in range(l-1):
    min=info[i][1]
    m=info[i]
    t=i
    for j in range(i+1,l):
        if min>info[j][1]:
            min=info[j][1]
            t=j
    info[i]=info[t]
    info[t]=m
print(info[0][1])

### FIXED CODE ###

D,G=map(int,input().split()) 
box=[] 
for i in range(D): 
    box.append(list(map(int,input().split()))) 
box.insert(0,[0,0]) #数を１番目に合わせるため 
info=[[0,0] for i in range(2**D)] #各全完の組での点数、解いた問題数の記憶
info2=[[0]*(D+1) for i in range(2**D)] #i番目を何問解いているか？

for i in range(2**D): #全完したものをinfoに追加
    for j in range(1,D+1): #100j点の問題は全完するか 
        if (i>>(j-1))&1: 
            info[i][0]+=box[j][1]+j*100*box[j][0] 
            info[i][1]+=box[j][0] 
            info2[i][j]=box[j][0] #ｊ番目を全問解いている。

for i in range(2**D):
    score=G-info[i][0]
    if score<=0:
        continue
    else:
        n=D
        while score>0:
            num=box[n][0]-info2[i][n] #残りの問題数
            #print(num)
            #print(str(i)+":"+str(score))
            if num!=0:
                for j in range(1,num+1):
                    score -= 100*n
                    info[i][1]+=1 #解いた数を増やす
                    if j==num: #ボーナス点追加
                        score-=box[n][1]
                    if  score<=0:
                        break
            n-=1
            
l=len(info)
for i in range(l-1):
    min=info[i][1]
    m=info[i]
    t=i
    for j in range(i+1,l):
        if min>info[j][1]:
            min=info[j][1]
            t=j
    info[i]=info[t]
    info[t]=m
print(info[0][1])
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
cost=sum(A)
for i in range(M):
    if A[N-1]%2==0:
        cost-=A[N-1]//2
    else:
        cost=cost-A[N-1]//2-1
    A[N-1]=A[N-1]//2
    if A[N-2]>A[N-1]:
        A.sort()
print(cost)

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
A=[-1*int(i) for i in input().split()]
heapq.heapify(A)
for _ in range(M):
    a=-1*heapq.heappop(A)
    a=a//2
    heapq.heappush(A,-1*a)
print(-1*sum(A))
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
ans=n
for i in range(1,n):
    for j in range(i,-1,-1):
        if l[i]>l[j]:
            ans-=1
            break
print(ans)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
ans=0
tmp=l[0]
for i in range(n):
    if tmp>=l[i]:
      tmp=l[i]
      ans+=1
print(ans)
### BUGGY CODE ###

N = int(input())

S = []
counter = 0
for i in range(N):
    S.append(input())
    temp = 0
    for j in range(i):
        if S[j] == S[i]:
            temp = 1
            break

    if temp == 0:
        counter += 1
print(counter)


### FIXED CODE ###

N = int(input())

S = []
counter = 0
for i in range(N):
    S.append(input())

S = sorted(S)
for i in range(N-1):
    if S[i] == S[i+1]:
        counter += 1
print(N - counter)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
if(A[-1] == 0):
  print(0)
else:
  p = 1
  for An in A:
    p *= An
  if(p > 10 ** 18):
    print(-1)
  else:
    print(p)

### FIXED CODE ###

t = int(input())
list_v = list(map(int,input().split()))
 
res = 1
if 0 in list_v:
  res = 0
else:
  for v in list_v:
    res *= v
    if res > 10**18:
      res = -1
      break
print(res)
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))

l = [0]*(N-K+1)
for i in range(N-K+1):
  l[i] = (sum(p[i:i+K])+K)/2
  
print(max(l))

### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
  
# 「和の期待値」は「期待値の和」なので、先に期待値を求める
for i in range(N):
  p[i] = (1+p[i])/2

# 累積和
S = [0]*N
S[0] = p[0]
for i in range(N-1):
  S[i+1] = S[i] + p[i+1]

ans = S[K-1]
for i in range(N-K):
  ans = max(ans, S[i+K] - S[i])

print(ans)
### BUGGY CODE ###

import fractions
from functools import reduce

n=int(input())
c = list(map(int, input().split()))
mod=10**9+7

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

v=lcm(*c)
ans=0

for i in range(n):
    ans+=v//c[i]
    ans%=mod
print(ans)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
import fractions
from functools import reduce

n=int(input())
c = list(map(int, input().split()))
mod=pow(10,9)+7

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

v=lcm(*c)%mod
ans=0

for i in range(n):
    ans += v * pow(c[i],mod-2,mod)
    ans%=mod

print(ans%mod)
### BUGGY CODE ###

from itertools import *

N,C=map(int,input().split())
D=[list(map(int,input().split())) for i in range(C)]
c=[list(map(int,input().split())) for i in range(N)]

lst=[[],[],[]]

for y in range(N):
    for x in range(N):
        lst[(y+x)%3].append(c[y][x])


Revalue=10**18
for Color1,Color2,Color3 in list(permutations(list(range(1,C+1)),3)):
    value=0
    for i in lst[0]:
        value+=D[i-1][Color1-1]
    for i in lst[1]:
        value+=D[i-1][Color2-1]
    for i in lst[2]:
        value+=D[i-1][Color3-1]
    Revalue=min(Revalue,value)
print(Revalue)


### FIXED CODE ###

from itertools import *
N,C=map(int,input().split())
D=[list(map(int,input().split())) for i in range(C)]
c=[list(map(int,input().split())) for i in range(N)]

lst=[[],[],[]]

for y in range(N):
    for x in range(N):
        lst[(y+x)%3].append(c[y][x])


Revalue=10**18

valuelst=[[0 for i in range(C)] for i in range(3)]
for v in range(3):
    for Color in range(1,C+1):
        value=0
        for i in lst[v]:
            value+=D[i-1][Color-1]
        valuelst[v][Color-1]=value


for Color1,Color2,Color3 in list(permutations(list(range(1,C+1)),3)):
    value=valuelst[0][Color1-1]+valuelst[1][Color2-1]+valuelst[2][Color3-1]

    Revalue=min(Revalue,value)
print(Revalue)
### BUGGY CODE ###

s = input()
n = len(s)
num = 2019
ans = 0
for i in range(n-3):
  for j in range(i+4,n+1):
    a = int(s[i:j])
    if a%num == 0:
      ans += 1
print(ans)

### FIXED CODE ###

def main():
  s = input()[::-1]
  l = len(s)
  n = 2019
  dp = [0]*n
  wk = 0
  r = 1
  for i in range(l):
    wk += int(s[i])*r
    wk %= n
    dp[wk] += 1
    r*= 10
    r %= n
  print(dp[0]+sum([i*(i-1)//2 for i in dp]))
main()
### BUGGY CODE ###

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
b = a[::-1]

ok, ng = -10**19, 10**19
while abs(ng-ok) > 1:
	x = (ng+ok)//2
	res = 0
	for c in a:
		if c*c < x:
			res -= 1
		if c == 0:
			if x > 0:
				res += n
		elif c > 0:
			#res += bisect(a, x/c - 1e-18)
			if c * a[0] >= x:
				pass
			else:
				l, r = 0, n
				while r-l > 1:
					y = (l+r)//2
					if a[y]*c < x:
						l = y
					else:
						r = y
				res += l+1
		else:
			#res += n - bisect(a, x/c + 1e-18)
			if c * b[0] >= x:
				pass
			else:
				l, r = 0, n
				while r-l > 1:
					y = (l+r)//2
					if b[y]*c < x:
						l = y
					else:
						r = y
				res += l+1
	res //= 2
	#print(x, res)
	if res < k:
		ok = x
	else:
		ng = x

print(ng-1)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
plus, zero, minus = [], [], []
for x in a:
	if x > 0:
		plus.append(x)
	elif x == 0:
		zero.append(x)
	else:
		minus.append(x)
m, z, p = len(minus), len(zero), len(plus)
mm, zz, pp = m * p, z * (m + p) + (z * (z - 1)) // 2, (m * (m-1)) // 2 + (p * (p-1)) // 2
plus.sort()
plus2 = plus[::-1]
minus.sort()
minus2 = minus[::-1]
#print(mm, zz, pp)

if mm + zz >= k and mm < k:
	print(0)
elif mm >= k:
	ok, ng = -10**19, 0
	while ng-ok > 1:
		x = (ng+ok)//2
		res = 0
		l = 0
		for c in plus:
			if l == m:
				res += m
			elif minus[l] * c >= x:
				res += l
			else:
				while minus[l] * c < x:
					l += 1
					if l == m:
						break
				res += l
		if res < k:
			ok = x
		else:
			ng = x
	print(ng-1)
else:
	ok, ng = 0, 10**19
	while ng-ok > 1:
		x = (ng+ok)//2
		lm, lp = 0, 0
		res = 0
		for c in minus:
			if c*c < x:
				res -= 1
			if lm == m:
				res += m
			elif minus2[lm] * c >= x:
				res += lm
			else:
				while minus2[lm] * c < x:
					lm += 1
					if lm == m:
						break
				res += lm
		for c in plus2:
			if c*c < x:
				res -= 1
			if lp == p:
				res += p
			elif plus[lp] * c >= x:
				res += lp
			else:
				while plus[lp] * c < x:
					lp += 1
					if lp == p:
						break
				res += lp
		res //= 2
		res += zz + mm
		#print(x, res)
		if res < k:
			ok = x
		else:
			ng = x
	print(ng-1)
### BUGGY CODE ###

# YouTube
def main():
    n = int(input())
    s = input()
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for i, c in enumerate(s[:-1]):
        for j in range(i + 1, n):
            if c == s[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
    ans = 0
    for d in range(n // 2 + 1, 0, -1):
        if ans >= d: break
        for i in range(n - d + 1):
            a = min(d, dp[i][i + d])
            ans = max(a, ans)
    print(ans)

main()


### FIXED CODE ###

# YouTube
def main():
    n = int(input())
    s = input()
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for i, c in enumerate(s):
        for j in range(n):
            if c == s[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
    ans = 0
    for i in range(n):
        for j in range(i+1,n+1):
            tmp=min(dp[i][j],j-i)
            ans=max(tmp,ans)
    print(ans)

main()
### BUGGY CODE ###

S = input()
L = len(S)
cnt = 0

li = [0]
for i in range(L):
    li.append(li[-1]+int(S[i]))

li.append(li[-1])

for i in range(0,L-3):
    for j in range(i+4,L+1):
        if (li[j]-li[i]) % 3 == 0:
            integer = int(S[i:j])
            if integer % 673 == 0:
                cnt += 1

print(cnt)


### FIXED CODE ###

from collections import Counter

S = input()
n = len(S)

dp = [0]*(n+1)

dp[n-1] = int(S[-1])

for i in range(n-2,-1,-1):
    dp[i] = (dp[i+1]+pow(10,n-i-1,2019)*int(S[i]))%2019

ans = Counter(dp)
cnt = 0
for i in ans.values():
    cnt += i*(i-1)//2
    
print(cnt)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
idx = 0
count = 0
for i in range(n):
  if idx >= n:
    break
  for j in range(n, 0, -1):
    if a[idx:j] == sorted(a[idx:j]) or a[idx:j] == sorted(a[idx:j], reverse=True):
      idx += len(a[idx:j])
      count += 1
      break
print(count)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
# 0: 1:増加 2:減少
state = 0
count = 1
for i in range(1, n):
  if state == 0:
    if a[i-1] < a[i]:
      state = 1
    elif a[i-1] > a[i]:
      state = 2
  elif state == 1:
    if a[i-1] > a[i]:
      state = 0
      count += 1
  else:
    if a[i-1] < a[i]:
      state = 0
      count += 1
print(count)
### BUGGY CODE ###

# Training CampTraining Camp
N = int(input())

p = 1
for i in range(1, N+1):
    p = p * i

p = float(p % (10**9 + 7))
print(int(p))

### FIXED CODE ###

# Training CampTraining Camp
N = int(input())

p = 1
for i in range(1, N+1):
    p = p * i
    p = float(p % (10**9 + 7))

print(int(p))
### BUGGY CODE ###

from collections import deque
def g(x):
    if len(x)==1:
        return x,0
    y = int(x[0])+int(x[1])
    if y<=9:
        return str(y),1
    else:
        z = int(str(y)[0])+int(str(y)[1])
        return str(z),2
def f(d,c):
    if c==1:
        return str(d),0
    if c==2:
        return g(str(d)+str(d))
    if c%2==0:
        x,n = f(d,c//2)
        return g(x+x)[0],2*n+g(x+x)[1]
    else:
        x,n = f(d,(c-1)//2)
        y,m = g(x+x)
        return g(y+str(d))[0],2*n+m+g(y+str(d))[1]
M = int(input())
x = deque([])
cnt = 0
for _ in range(M):
    d,c = map(int,input().split())
    y,n = f(d,c)
    x.append(y)
    cnt += n
while len(x)>1:
    y0 = x.popleft()
    y1 = x.popleft()
    y,n = g(y0+y1)
    x.appendleft(y)
    cnt += n
print(cnt)

### FIXED CODE ###

def g(i,j):
    if i+j<10:
        return 1,i+j
    else:
        a = i+j
        b = a%10+a//10
        return 2,b
def f(c,d):
    if d==1:
        return 0,c
    if d==2:
        return g(c,c)
    if d%2==0:
        a,b = f(c,d//2)
        x,y = g(b,b)
        return 2*a+x,y
    else:
        a,b = f(c,(d-1)//2)
        x1,y1 = g(b,b)
        x2,y2 = g(c,y1)
        return 2*a+x1+x2,y2
M = int(input())
A = [list(map(int,input().split())) for _ in range(M)]
cnt = 0
B = []
for i in range(M):
    c,d = A[i][0],A[i][1]
    a,b = f(c,d)
    cnt += a
    B.append(b)
b = B[0]
for i in range(1,M):
    a,b = g(b,B[i])
    cnt += a
print(cnt)
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0

    for i in range(N):
        for j in range(1+i, N):
            if i == j:
                continue
            else:
                ans += A[i] * A[j]
    print(ans % 1000000007)
main()


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    all_sum = sum(A) ** 2
    st = 0
    for i in range(N):
        st += A[i] ** 2
    print(int(((all_sum - st)//2) % 1000000007))
main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000000)

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

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

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

def solve():
    L, a, b, M = map(int, input().split())
    X = 0
    s = a
    nd = -1
    ne = 0
    for d in range(1, 19):
        ne = min((pow(10, d) - a - 1) // b, L-1)
        if ne == 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

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

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

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

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

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

if __name__ == "__main__":
    solve()
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))

k = 1000000007

ans = 0
for s in range(len(A)-1):
    ans += A[s]*sum(A[s+1:])

if ans>1000000007:
    print(ans%k)
else:
    print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))

k = 1000000007

sm = sum(A)

ans = 0
for s in range(len(A)-1):
    #ans += A[s]*sum(A[s+1:])
    sm -= A[s]
    ans += A[s]*sm

if ans>1000000007:
    print(ans%k)
else:
    print(ans)
### BUGGY CODE ###

import sys
from collections import Counter

read = sys.stdin.buffer.read


def divisors(n):
    lower = []
    upper = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            lower.append(i)
            if i != n // i:
                upper.append(n // i)

    lower.extend(reversed(upper))
    return lower


def main():
    N, *A = map(int, read().split())
    C = Counter(A)
    A_set = set(A)

    ans = 0
    for a in A_set:
        if C[a] != 1:
            continue
        D = divisors(a)
        if all(d not in A_set for d in D[:-1]):
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, *A = map(int, read().split())
    A.sort()

    M = 10 ** 6
    B = [True] * (M + 1)
    B[0] = False
    ans = 0
    for i in range(N):
        if not B[A[i]]:
            continue
        if i < N - 1 and A[i + 1] == A[i]:
            B[A[i]] = False
        else:
            ans += 1
        for n in range(2 * A[i], M + 1, A[i]):
            B[n] = False

    print(ans)
    return


if __name__ == '__main__':
    main()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(1,n+1):
    print(a.count(i))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i in a:
    b[i-1]+=1
[print(i) for i in b]
### BUGGY CODE ###

import sys
input=sys.stdin.readline
h,w=map(int,input().split())
g=[list(input()) for _ in range(h)]
q=[]
r=[[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if g[i][j]=="#":
            g[i][j]=0
            r[i][j]=1
            q.append([i,j])
dx=[1,-1,0,0]
dy=[0,0,1,-1]
ans=0
while q:
    i,j=q.pop(0)
    for x,y in zip(dx,dy):
        if i+y<0 or i+y>=h or j+x<0 or j+x>=w:
            continue
        if r[i+y][j+x]:
            continue
        g[i+y][j+x]=g[i][j]+1
        r[i+y][j+x]+=1
        ans=max(ans,g[i+y][j+x])
        q.append([i+y,j+x])
print(ans)


### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
a=[input() for _ in range(h)]
dxy=[(0,1),(1,0),(-1,0),(0,-1)]
inf=float("inf")

dp=[[inf]*w for _ in range(h)]
q=deque()

for y,l in enumerate(a):
    for x,c in enumerate(l):
        if c=="#":
            dp[y][x]=0
            q.append((x,y))
ans=0
while q:
    x,y=q.popleft()
    d=dp[y][x]
    for dx,dy in dxy:
        nx,ny=x+dx,y+dy
        if not 0<=nx<w: continue
        if not 0<=ny<h: continue
        if dp[ny][nx]<=d+1: continue
        dp[ny][nx]=d+1
        q.append((nx,ny))
        ans=max(ans,d+1)
print(ans)