output_description: Print the remainder when the integer obtained by concatenating the terms is
  divided by M.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      L A B M
attempt: import sys
  from math import ceil
  from functools import lru_cache
  
  
  def input():
      return sys.stdin.readline().strip()
  
  
  sys.setrecursionlimit(10**6)
  
  
  @lru_cache(maxsize=1024)
  def power(n, mod):  # 10 ** n % mod
      return pow(10, n, mod)
  
  
  @lru_cache(maxsize=1024)
  def f(L, d, mod):
      if L == 0:
          val = 0
      elif L == 1:
          val = 1
      elif L % 2 == 0:
          val = (f(L // 2, d, mod) * power(L * d // 2, mod) + f(L // 2, d, mod)) % mod
      elif L % 2 != 0:
          val = (f(L - 1, d, mod) * power(d, mod) + 1) % mod
      # print("f({}, {})={}".format(L, d, val))
      return val
  
  
  @lru_cache(maxsize=1024)
  def g(L, d, B, mod):
      if L == 0:
          val = 0
      elif L == 1:
          val = 0
      elif L % 2 == 0:
          val = (
              g(L // 2, d, B, mod) * power(L * d // 2, mod)
              + g(L // 2, d, B, mod)
              + (B * L // 2) * f(L // 2, d, mod)
          ) % mod
      elif L % 2 != 0:
          val = (g(L - 1, d, B, mod) * power(d, mod) + B * (L - 1)) % mod
      # print("g({}, {})={}".format(L, d, val))
      return val
  
  
  def main():
      L, A, B, mod = map(int, input().split())
  
      """
      数列の桁が変わっていくのが面倒だが、桁数dの数列の要素の個数は
          (10^(d+1)未満の要素の個数) - (10^d未満の要素の個数)
      で簡単に求まるので、とりあえず桁数は同じで考えて良い
  
      このとき求めるのは
          \Sum_{i=0}^{L-1} (A+Bi) * 10^{d(L-i-1)}
      これは分解すれば
          f(L) = \Sum_{i=0}^{L-1} 10^{di}
          g(L) = \Sum_{i=0}^{L-1} Bi * 10^{d(L-i-1)}
      の線形和(= A * f(L) + g(L))として求まる。
  
      前者については
          f(L + 1) = f(L) * 10^d + 1
          f(L * 2) = f(L) * 10^{Ld} + f(L)
      が成り立つので二分法によりO(log^2 L)で求まる（f(18)->f(9)->f(8)->f(4)->f(2)->f(1)みたいに）
  
      後者については
          g(L + 1) = g(L) * 10^d
          g(L * 2) = g(L) * 10^{Ld} + g(L) + (BL * f(L))
      なのでやはり同様に二分法が可能でO(log^3 L)で計算可能。
      """
  
      # まずは桁数で区切る
      initial = [0] * 19  # initial[d] = (数列の項でd桁にはじめてなる項の値)
      number = [0] * 19  # number[d] = (数列の項でd桁である物が何個存在するか)
  
      for d in range(len(str(A)), 19):
          i = max(0, ceil((10 ** (d - 1) - A) / B))
          initial[d] = A + B * i
          if (10**d - A) % B == 0:
              number[d] = (10**d - A) // B - i
          else:
              number[d] = (10**d - A) // B - i + 1
          if number[d] == 0:
              initial[d] = 0
  
      max_len = len(str(A + B * (L - 1)))
      exceeded_num = sum(number[: (max_len + 1)]) - L
      number[max_len] -= exceeded_num
      initial[(max_len + 1) :] = [0] * (18 - max_len)
      number[(max_len + 1) :] = [0] * (18 - max_len)
      # print("initial={}".format(initial))
      # print("number={}".format(number))
  
      # 各dについて上述の値を計算
      ans = 0
      digits = 0
      for d in range(18, 0, -1):
          a = initial[d]
          l = number[d]
          val = (a * f(l, d, mod) + g(l, d, B, mod)) * power(digits, mod)
          val %= mod
          ans += val
          ans %= mod
          digits += d * l
          # print("d={}->val={}".format(d, val))
      print(ans)
  
  
  if __name__ == "__main__":
      main()
  
problem_description: Statement
  
  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?
samples: [{"input": "5 3 4 10007", "output": "5563\n    \n\nOur arithmetic progression is 3, 7, 11, 15, 19, so the answer is 37111519 mod\n10007, that is, 5563.\n\n* * *"}, {"input": "4 8 1 1000000", "output": "891011\n    \n\n* * *"}, {"input": "107 10000000000007 1000000000000007 998244353", "output": "39122908"}]