output_description: Print the number of non-empty (contiguous) substrings of S that are divisible
  by P when regarded as an integer written in base ten.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N P
      S
attempt: from collections import Counter
  
  N, P = list(map(int, input().split()))
  S = [int(c) for c in input().rstrip()]
  
  
  if P in [2, 5]:
      total = 0
      for i, x in enumerate(S):
          if x % P == 0:
              # If P == 2
              # all substring ending here with last digit even
              # If P == 5
              # all substring ending here with last digit 5 or 0
              total += i + 1
      print(total)
  else:
      # Note P is relatively prime with 10
  
      # If S is '1234'
      # Want suffixes:
      # s[4] = 1234
      # s[3] =  234
      # s[2] =   34
      # s[1] =    4
      # s[0] =    0
      #
      # Then s[j] - s[i] gives the value of the number int(S[-j:-i]) * 10**(N -i)
      # Since P doesn't divide 10, if P divides s[j] - s[i] it also divides the number
  
      CHECK = False
      suf = [0]
      power = 1
      for x in reversed(S):
          suf.append(suf[-1] + x * power)
          power *= 10
          if not CHECK:
              # Don't mod when checking
              suf[-1] %= P
              power %= P
      if CHECK:
          # Check
          N = len(S)
          for i in range(N):
              for j in range(i + 1, N + 1):
                  print(
                      i,
                      j,
                      int("".join(map(str, S[N - j : N - i]))) * (10**i),
                      suf[j] - suf[i],
                  )
          print(suf)
  
      # Count number of s[j] - s[i] pairs that are 0 mod P
      total = 0
      counts = Counter()
      for x in suf:
          x = x % P
          total += counts[x]
          counts[x] += 1
      print(total)
  
problem_description: Statement
  
  Takahashi has a string S of length N consisting of digits from `0` through
  `9`.
  
  He loves the prime number P. He wants to know how many non-empty (contiguous)
  substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P
  when regarded as integers written in base ten.
  
  Here substrings starting with a `0` also count, and substrings originated from
  different positions in S are distinguished, even if they are equal as strings
  or integers.
  
  Compute this count to help Takahashi.
samples: [{"input": "4 3\n    3543", "output": "6\n    \n\nHere S = `3543`. There are ten non-empty (contiguous) substrings of S:\n\n  * `3`: divisible by 3.\n\n  * `35`: not divisible by 3.\n\n  * `354`: divisible by 3.\n\n  * `3543`: divisible by 3.\n\n  * `5`: not divisible by 3.\n\n  * `54`: divisible by 3.\n\n  * `543`: divisible by 3.\n\n  * `4`: not divisible by 3.\n\n  * `43`: not divisible by 3.\n\n  * `3`: divisible by 3.\n\nSix of these are divisible by 3, so print 6.\n\n* * *"}, {"input": "4 2\n    2020", "output": "10\n    \n\nHere S = `2020`. There are ten non-empty (contiguous) substrings of S, all of\nwhich are divisible by 2, so print 10.\n\nNote that substrings beginning with a `0` also count.\n\n* * *"}, {"input": "20 11\n    33883322005544116655", "output": "68"}]