Submission #6215809

---

Source Code Expand

from functools import lru_cache
N = int(input())
AL = [[int(x) for x in input().split()] for _ in range(N)]
MOD = int(input())


# 10^nの事前計算, 平方分割
M = 10 ** 5
pow_10 = [1]
x = 1
for _ in range(M):
  x *= 10
  x %= MOD
  pow_10.append(x)
pow_10M = [1]
r = pow_10[M]
x = 1
for _ in range(M):
  x *= r
  x %= MOD
  pow_10M.append(x)

def power(n):
  # pow(10,n,MOD)
  q,r = divmod(n,M)
  x,y = pow_10M[q], pow_10[r]
  return x*y%MOD

@lru_cache(None)
def rep(d,n):
  # dが桁数
  # 1000100010001000
  if n == 0:
    return 0
  x = rep(d,n//2)
  x *= (power(n//2*d) + 1)
  if n&1:
    x *= power(d)
    x += 1
  x %= MOD
  return x

answer = 0
for a,n in AL:
  d = len(str(a))
  answer *= power(d*n)
  answer += rep(d,n) * a
  answer %= MOD
  
print(answer)

Submission Info

Judge Result