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: #!/usr/bin/env python
  
  
  class subset:
      def __init__(self, string):
          self.string = string
          self.len = len(string)
          self.split = int((self.len + 1) / 2)
          if self.len == 1:
              self.half = [self]
          else:
              self.half = [subset(string[: self.split]), subset(string[self.split :])]
          self.msum = None
          self.msumr = None
  
      def get_msum(self):
          if self.msum is not None:
              return self.msum
          if self.len == 1:
              return [int(self.string) % p]
          else:
              self.msum = self.half[1].get_msum()
              add = self.msum[-1]
              self.msum.extend(
                  [(v * dm[self.half[1].len] + add) % p for v in self.half[0].get_msum()]
              )
  
              # self.msum = [
              #     (v * dm[self.half[1].len] + self.half[1].get_msum()[-1]) % p
              #     for v in self.half[0].get_msum()
              # ]
              # self.msum.extend(self.half[1].get_msum())
              return self.msum
  
      def get_msumr(self):
          if self.msumr is not None:
              return self.msumr
          if self.len == 1:
              return [int(self.string) % p]
          else:
              self.msumr = self.half[0].get_msumr()
              add = self.msumr[-1]
              self.msumr.extend(
                  [
                      (add * dm[i + 1] + v) % p
                      for i, v in enumerate(self.half[1].get_msumr())
                  ]
              )
              return self.msumr
  
      def get_primnum(self):
          global p
          if self.len == 1:
              if int(self.string) % p == 0:
                  return 1
              else:
                  return 0
          c = self.half[0].get_primnum() + self.half[1].get_primnum()
          rc = [0] * p
          for a in self.half[0].get_msum():
              rc[a] += 1
          # print(self.string, rc)
          for i, b in enumerate(self.half[1].get_msumr()):
              idx = (-b * dmi[i + 1]) % p
              # print(i, b, idx)
              c += rc[idx]
          return c
  
  
  def mypow(n, m, p):
      if m == 0:
          return 1
      elif m % 2 == 0:
          return (mypow(n, int(m / 2), p) ** 2) % p
      elif m % 2 == 1:
          return (mypow(n, int(m / 2), p) ** 2 * n) % p
  
  
  n, p = (int(val) for val in input().split())
  string = input()
  
  m = []
  dm = []
  dmi = []
  
  for i in range(n):
      if i == 0:
          dm.append(1)
      else:
          dm.append((dm[i - 1] * 10) % p)
      dmi.append(mypow(dm[i], p - 2, p))
  ss = subset(string)
  print(ss.get_primnum())
  
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"}]