Harryxun/stf_run huggingface dataset:
import sys
import math
N,M = [int(n) for n in input().split()]
S = str(input())
T = str(input())

def lcm(N,M):
    return(N*M/math.gcd(N,M))

if (N % M == 0 or M % N == 0):
    if S!= T:
        print(-1)
        sys.exit()
else:
    print(int(lcm(N,M)))


### FIXED CODE ###

import sys
N,M = [int(n) for n in input().split()]
S = str(input())
T = str(input())

# N < M
def gcd(N,M):
    if(N > M):
        tmp = N
        N = M
        M = tmp
    r = M % N
    while(r != 0):
        M = N
        N = r
        r = M%N
    return N

def lcm(N,M):
    return(N*M/gcd(N,M))

if (N % M == 0):
    if S == T:
        print(M)
    else:
        p = int(N/M)
        for i in range(M):
            if T[i] != S[i*p]:
                print(-1)
                sys.exit()
        print(N)
elif (M % N == 0):
    if S == T:
        print(M)
    else:
        p = int(M/N)
        for i in range(N):
            if S[i] != T[i*p]:
                print(-1)
                sys.exit()
        print(M)
else:
    mngcd = gcd(N,M)
    k = int(N/mngcd)
    m = int(M/mngcd)
    for i in range(mngcd):
        if S[i*k] != T[i*m]:
            print(-1)
            sys.exit()
    print(int(lcm(N,M)))
n = int(input())
s = input()
x = int(s, 2)
p = s.count("1")
pre0, pre1 = x%(p-1), x%(p+1)

nxt = [i for i in range(n+10)]
for i in range(1, n+10):
	nxt[i] %= bin(i).count("1")

for i in range(n):
	if x == 1<<(n-1-i):
		print(0)
		continue
	if s[i] == "0":
		tmp = (pre1 + pow(2, n-1-i, p+1)) % (p+1)
	else:
		tmp = (pre0 - pow(2, n-1-i, p-1)) % (p-1)
	ans = 1
	while tmp > 0:
		ans += 1
		tmp = nxt[tmp]
	print(ans)

### FIXED CODE ###

n = int(input())
s = input()
x = int(s, 2)
p = s.count("1")
if p > 1:
	pre0 = x%(p-1)
pre1 = x%(p+1)

nxt = [i for i in range(n+10)]
for i in range(1, n+10):
	nxt[i] %= bin(i).count("1")

for i in range(n):
	if x == 1<<(n-1-i):
		print(0)
		continue
	if s[i] == "0":
		tmp = (pre1 + pow(2, n-1-i, p+1)) % (p+1)
	else:
		tmp = (pre0 - pow(2, n-1-i, p-1)) % (p-1)
	ans = 1
	while tmp > 0:
		ans += 1
		tmp = nxt[tmp]
	print(ans)
import math
phi = (1 + math.sqrt(5)) / 2

def counter(n):
    if n == 1:
        return 0
    else:
        f = round(phi**(n) / math.sqrt(5)) % (10**9+7)
        return f

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
ans = round(phi**(a[0]) / math.sqrt(5)) % (10**9+7)
print(ans)
for i in range(1,M):
    ans = (ans * counter(a[i]-a[i-1]-1)) % (10**9+7)

ans = ans * round(phi**(N-a[-1]) / math.sqrt(5)) % (10**9+7)

print(ans)

### FIXED CODE ###

def fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        a = 1
        b = 0
        for _ in range(n-1):
            (a, b) = (a+b, a)
        return a % (10 ** 9 + 7)


def counter(n):
    if n == 0:
        return 0
    else:
#        f = round(phi**(n) / math.sqrt(5)) % (10**9+7)
        return fib(n)


N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
if M == 0:
    print(counter(N+1))
    exit()
a.append(N+1)
ans = counter(a[0])
for i in range(1,M+1):
    ans = (ans * counter(a[i]-a[i-1]-1)) % (10**9+7)
print(ans)
N = int(input())
M = int(input())
total = 0

for i in range(M):
  	A = int(input())
    total = total + A
    
if total <= N:
    print (N - total)
else:
  	print "-1"

### FIXED CODE ###

import math

n, m = map(int, input().split())
a = list(map(int, input().split()))

if (n-sum(a)) < 0:
    print(-1)
else:
    print(n-sum(a))
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,M = LI()

    d = {}
    m = M
    for i in range(2,int(math.sqrt(M))+1):
        while m % i == 0:
            if i in d:
                d[i] += 1
            else:
                d[i] = 1
            m //= i
    if m > 1:
        d[m] = 1

    a = [0]
    b = [0]
    c = 1
    for i in range(1,N+int(math.log(N,2))**2+1):
        c = (c * i) % MOD
        a.append(c)
        b.append(pow(c,MOD-2,MOD))

    ans = 1
    for v in d.values():
        ans = (ans * a[N+v-1] * b[v]* b[N-1]) % MOD
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()

    d = {}
    m = M
    for i in range(2,int(math.sqrt(M))+1):
        while m % i == 0:
            if i in d:
                d[i] += 1
            else:
                d[i] = 1
            m //= i
    if m > 1:
        d[m] = 1

    a = [1]
    b = [1]
    c = 1
    for i in range(1,N+int(math.log(M,2)) +1):
        c = (c * i) % MOD
        a.append(c)
        b.append(pow(c,MOD-2,MOD))

    ans = 1
    for v in d.values():
        ans = (ans * a[N+v-1] * b[v]* b[N-1]) % MOD
    print(ans)

if __name__ == '__main__':
    main()
from fractions import math

k = int(input())

g =[gcd(math.gcd(i+1, j+1), l+1) for i in range(k) for j in range(k) for l in range(k)]
print(sum(g))

### FIXED CODE ###

import math
k = int(input())

sm=0
for i in range(1,k+1):
    for l in range(1,k+1):
        gcdab=math.gcd(i,l)
        for m in range(1,k+1):
            sm+=math.gcd(gcdab,m)

print(sm)
LARGE = 1000000007


def step(a, i):
    if i == len(a):
        return 1
    elif i > len(a):
        return 0

    elif a[i] == 0:
        return 0

    return step(a, i + 1) + step(a, i + 2)


def solve():
    n, m = [int(x) for x in input().split()]
    a = [1] * n
    for _ in range(m):
        a[int(input()) - 1] = 0

    # print(n, m)
    # print(a)
    # ans = step(a, 0)

    f = [0] * n
    if a[0] == 0:
        f[0] = 0
        if a[1] == 0:
            f[1] = 0
        else:
            f[1] = 1
    else:
        a[0] = 1
        if a[1] == 0:
            f[1] = 0
        else:
            f[1] = 2

    if a[1] == 0:
        f[1] = 0

    # print(f)
    for i in range(2, n):
        # print(i)
        if a[i]:
            f[i] = (f[i-1] % LARGE) + (f[i-2] % LARGE)
    # print(f)
    print(f[n-1])


if __name__ == '__main__':
    solve()


### FIXED CODE ###

# inputs
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

# solve
dp = [1] * (n+1)

for i in a:
    dp[i] = 0

for i in range(2, n+1):
    if dp[i] != 0:
        dp[i] = (dp[i - 1] + dp[i - 2]) % (10 ** 9 + 7)

print(dp[n])
n = int(input())
s = input()
print('red' if a < 3200 else s)

### FIXED CODE ###

n = int(input())
s = input()
print('red' if n < 3200 else s)
(W, H, x, y, r) = [int(i) for i in input().split()

### FIXED CODE ###

nums = input().split()
W = int( nums[0])
H = int( nums[1])
x = int( nums[2])
y = int( nums[3])
r = int( nums[4])
    
if (x - r) >= 0 and (x + r) <= W:
    if (y - r) >= 0 and (y + r) <= H:
        print( "Yes")
    else:
        print( "No")
else:
    print( "No")
def main():
    N = int(input())
    print(solve(N))


def count(n, start, end):
    """n以下の数字でsで始まりeで終わる数字の個数
    732, 1, 2 -> 12, 102, 112, 122, ... , 192 = 11
    Examples:
        >>> count(732, 1, 2)
        11
        >>> count(25, 1, 1)
        2
        >>> count(25, 3, 3)
        1
        >>> count(100, 1, 2)
        1
        >>> count(102, 1, 2)
        2
    """

    if n <= 9:
        return 1 if start == end and start <= n else 0
    if n <= 99:
        one_digit = 1 if start == end else 0
        two_digit = 1 if start * 10 + end <= n else 0
        return one_digit + two_digit
    digit_length = len(str(n))
    # digit_length桁以下
    ret1 = count(10 ** (digit_length - 1) - 1, start, end)
    # digit_length桁
    min_cand = start * (10 ** (digit_length - 1)) + end
    if min_cand > n:
        return ret1
    ret2 = min((n-min_cand) // 10 + 1, 10 ** (digit_length - 2))
    return ret1 + ret2


def solve(n):
    """n以下の組で, (213, 382)のような末尾と先頭が等しい数の個数"""
    result = 0
    for i in range(1, 10):
        for j in range(i + 1, 10):
            result += 2 * count(n, i, j) * count(n, j, i)
    for i in range(1, 10):
        result += count(n, i, i) * count(n, i, i)
    return result


if __name__ == "__main__":
    assert_equal(count(732, 1, 2), 11)
    main()


### FIXED CODE ###

def main():
    N = int(input())
    print(solve(N))


def count(n, start, end):
    """n以下の数字でsで始まりeで終わる数字の個数
    732, 1, 2 -> 12, 102, 112, 122, ... , 192 = 11
    Examples:
        >>> count(732, 1, 2)
        11
        >>> count(25, 1, 1)
        2
        >>> count(25, 3, 3)
        1
        >>> count(100, 1, 2)
        1
        >>> count(102, 1, 2)
        2
    """

    if n <= 9:
        return 1 if start == end and start <= n else 0
    if n <= 99:
        one_digit = 1 if start == end else 0
        two_digit = 1 if start * 10 + end <= n else 0
        return one_digit + two_digit
    digit_length = len(str(n))
    # digit_length桁以下
    ret1 = count(10 ** (digit_length - 1) - 1, start, end)
    # digit_length桁
    min_cand = start * (10 ** (digit_length - 1)) + end
    if min_cand > n:
        return ret1
    ret2 = min((n-min_cand) // 10 + 1, 10 ** (digit_length - 2))
    return ret1 + ret2


def solve(n):
    """n以下の組で, (213, 382)のような末尾と先頭が等しい数の個数"""
    result = 0
    for i in range(1, 10):
        for j in range(i + 1, 10):
            result += 2 * count(n, i, j) * count(n, j, i)
    for i in range(1, 10):
        result += count(n, i, i) * count(n, i, i)
    return result


if __name__ == "__main__":
    main()
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

from decimal import Decimal

import numpy as np
S = str(input())
N = len(S)
A = np.matrix([[0]*N for _ in range(N)])
for i in range(N):
  if S[i]=='R':
    A[i,i+1] = 1
  else:
    A[i,i-1] = 1

x = np.array([1]*N) * np.linalg.matrix_power(A,10**100)
a = []
for i in range(N):
  a.append(x[0,i])
print(*a)

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

S = str(input())
n = len(S)
ans = [0]*n

left = 0
while left<=n-1:
  R_pos = n-1
  for i in range(left,n):
    if S[i]=='L':
      R_pos = i-1
      L_pos = i
      break
  if R_pos == n-1:
    ans[R_pos] += R_pos-left + 1
    break
  right = n-1
  for j in range(i+1,n):
    if S[j] == 'R':
      right = j-1
      break
  ans[R_pos] += (R_pos-left)//2 + (right-R_pos)//2 + 1
  ans[L_pos] += (L_pos-left)//2 + (right-L_pos)//2 + 1
  if right == n-1:
    break
  left = j

print(*ans)
n=int(input)
A=list(map(int,input().split()))
for a in A:
    if a%2==0:
        if a%3!=0 and a%5!=0:
            print('DENIED')
            exit()
print('APPROVED')

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
for a in A:
    if a%2==0:
        if a%3!=0 and a%5!=0:
            print('DENIED')
            exit()
print('APPROVED')
inp = input()
x, y = inp.split(' ')
print(x + y/2)

### FIXED CODE ###

x, y = [int(i) for i in input().split()]
print(int(x + y/2))
k, s = list(map(int, input().split()))

p = s
factors = {}

while p > 1:
    f = False
    for i in range(2, int(p**0.5)+1):
        if p % i == 0:
            if i in factors:
                factors[i] += 1
            else:
                factors[i] = 1

            p //= i
            f = True
            break

    if not f:
        if p in factors:
            factors[p] += 1
        else:
            factors[p] = 1
        break

primes = list(factors.keys())
exp = [0] * len(primes)
upper = s/k
ans = 1

while exp[0] <= factors[primes[0]]:
    num = 1
    for i in range(len(primes)):
        num *= pow(primes[i], exp[i])

    if num == upper:
        ans = num
        break
    elif num < upper:
        ans = max(ans, num)

    index = len(primes)-1
    done = False
    while not done:
        exp[index] += 1
        if exp[index] > factors[primes[index]]:
            if index == 0:
                break
            else:
                exp[index] = 0
                index -= 1
        else:
            done = True

print(ans)

### FIXED CODE ###

k, s = list(map(int, input().split()))

p = s
factors = {}

while p > 1:
    f = False
    for i in range(2, int(p**0.5)+1):
        if p % i == 0:
            if i in factors:
                factors[i] += 1
            else:
                factors[i] = 1

            p //= i
            f = True
            break

    if not f:
        if p in factors:
            factors[p] += 1
        else:
            factors[p] = 1
        break

if len(factors) == 0:
    print(1)
else:
    primes = list(factors.keys())
    exp = [0] * len(primes)
    upper = s/k
    ans = 1

    while exp[0] <= factors[primes[0]]:
        num = 1
        for i in range(len(primes)):
            num *= pow(primes[i], exp[i])

        if num == upper:
            ans = num
            break
        elif num < upper:
            ans = max(ans, num)

        index = len(primes)-1
        done = False
        while not done:
            exp[index] += 1
            if exp[index] > factors[primes[index]]:
                if index == 0:
                    break
                else:
                    exp[index] = 0
                    index -= 1
            else:
                done = True

    print(ans)
from dateutil.parser import parse
s = input()
inputDate = parse(s)
heiseiDate = parse('20190430')

if inputDate > heiseiDate:
    print('TBD')
else:
    print('Heisei')

### FIXED CODE ###

from datetime import datetime
s = input()
inputDate = datetime.strptime(s,'%Y/%m/%d')
heiseiDate = datetime.strptime('20190430','%Y%m%d')

if inputDate > heiseiDate:
    print('TBD')
else:
    print('Heisei')
r=input()
print(3.141*2*r)

### FIXED CODE ###

r=input()
print(3.141*2*int(r))
s = stdin.readline().rstrip()
ans = [0] * len(s)
c = 0
for i in range(len(s)):
    if s[i] == 'R':
        c += 1
    if s[i] == 'L' and s[i-1] == 'R':
        if c % 2 == 0:
            ans[i] += c // 2
            ans[i-1] += c // 2
        else:
            ans[i] += c//2
            ans[i-1] += c//2 + 1
        c = 0

for i in reversed(range(len(s))):
    if s[i] == 'L':
        c += 1
    if s[i] == 'R' and s[i+1] == 'L':
        if c % 2 == 0:
            ans[i+1] += c // 2
            ans[i] += c // 2
        else:
            ans[i+1] += c//2 + 1
            ans[i] += c // 2
        c = 0
print(' '.join(ans))

### FIXED CODE ###

s = input()
ans = [0] * len(s)
c = 0
for i in range(len(s)):
    if s[i] == 'R':
        c += 1
    if s[i] == 'L' and s[i-1] == 'R':
        if c % 2 == 0:
            ans[i] += c // 2
            ans[i-1] += c // 2
        else:
            ans[i] += c//2
            ans[i-1] += c//2 + 1
        c = 0
c = 0
for i in reversed(range(len(s))):
    if s[i] == 'L':
        c += 1
    if s[i] == 'R' and s[i+1] == 'L':
        if c % 2 == 0:
            ans[i+1] += c // 2
            ans[i] += c // 2
        else:
            ans[i+1] += c//2 + 1
            ans[i] += c // 2
        c = 0
print(' '.join(list(map(str, ans))))
s={'a': input(), 'b': input(), 'c' input()}
now='a'
while s[now]!="":
  next =s[now][0]
  s[now]=s[now][1:]
  now= next
print(now.upper())

### FIXED CODE ###

s = {'a': input(), 'b': input(), 'c': input()}
 
now = 'a'
while s[now] != '':
    next = s[now][0]
    s[now] = s[now][1:]
    now = next
print(now.upper())
def main():
  N = int(input())
  def count(n):
    ret = 0
    i = 1
    while i*i <= n:
      if n % i == 0:
        ret += 1
        if i != n // i:
          ret += 1
      i += 1
    return ret


  ans = 1
  l[0] = True
  l[1] = True
  if N==1:
    print(ans)
  else:
    for i in range(2,N+1):
      x = count(i)
      ans += x * i

    print(ans)
    
main()

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1, N + 1):
  x = N//i
  ans += i * x * (x + 1) // 2
  
print(ans)
a,b,c=map(int,input().split());print("YNeos"[a+b<c::2])

### FIXED CODE ###

a,b,c,d=[int(input())for i in range(4)];print([a,b][a>b]+[c,d][c>d])
A, P = map(int, input().split())

Apple = 3*A + P

if Apple % 2 == 0:
  ans = APPLE/2
else:
  ans = (Apple-1)/2

print(int(ans))

### FIXED CODE ###

A, P = map(int, input().split())
 
Apple = 3*A + P
 
if Apple % 2 == 0:
  ans = Apple/2
else:
  ans = (Apple-1)/2
 
print(int(ans))
x1 = int(input())
y1 = int(input())
x2 = int(input())
y2 = int(input())
v1x = x2 - x1
v1y = y2 - y1

v2x = -v1y
v2y = v1x
v3x = -v2y
v3y = v2x
x3 = x2 + v2x
y3 = y2 + v2y
x4 = x3 + v3x
y4 = y3 + v3y
print(x3, " ", y3, " ", x4, " ", y4)

### FIXED CODE ###

x1, y1, x2, y2 = map(int, input().split())
v1x = x2 - x1
v1y = y2 - y1

v2x = -v1y
v2y = v1x
v3x = -v2y
v3y = v2x
x3 = x2 + v2x
y3 = y2 + v2y
x4 = x3 + v3x
y4 = y3 + v3y
print(x3, y3, x4, y4)
weeks = {'MON': '1', 'TUE': '2',
    ...:  'WED': '3', 'THU': '4',
    ...:  'FRI': '5', 'SAT': '6',
    ...:  'SUN': '0'
    ...:  }
    ...: S = input('today:')
    ...: print(7-int(weeks.get(S)))

### FIXED CODE ###

weeks = {'MON': '1', 'TUE': '2', 'WED': '3', 'THU': '4', 'FRI': '5', 'SAT': '6', 'SUN': '0'}
s = input()
print(7-int(weeks.get(s)))
n = raw_input()
num = raw_input()
array = []
array = num.strip().split(" ")

for i in range(1, int(n)):
    print " ".join(array)
    v = array[i]
    j = i - 1
    while j >= 0 and array[j] > v:
        array[j + 1] = array[j]
        j -= 1
    array[j + 1] = v
print " ".join(array

### FIXED CODE ###


n = raw_input()
num = raw_input()
array = []
array = num.strip().split(" ")
int_array = map(int, array)

for i in range(1, int(n)):
    array = map(str, int_array)
    print " ".join(array)
    v = int_array[i]
    j = i - 1
    while j >= 0 and int_array[j] > v:
        int_array[j + 1] = int_array[j]
        j -= 1
    int_array[j + 1] = v
array = map(str, int_array)
print " ".join(array)
a,b = map(int, iput().split())
print(a if a<=b else a-1)

### FIXED CODE ###

a,b = map(int, input().split())
print(a if a<=b else a-1)
N = int(input())
M = str(input())

if len(N)>7:
    print(M[0:7]+'...')
else:
    print(M)

### FIXED CODE ###

N = int(input())
M = str(input())

if len(M)>N:
    print(M[0:N]+'...')
else:
    print(M)
n=int(input())

print((10**n-(9**n+9**n-8**n)%(10**9+7))

### FIXED CODE ###

n=int(input())

print((10**n-(9**n+9**n-8**n))%(10**9+7))
n = int(input())
max = 0
sum = 0

#print ("START")
for i in range(n):
	data = (input()
#	print("aaa")
	data = int(data)
#	print(data)
	if max < data:
		max = data
	sum = sum + data
print(sum - max//2)

### FIXED CODE ###

n = int(input())
max = 0
sum = 0

#print ("START")
for i in range(n):
	data = input()
#	print("aaa")
	data = int(data)
#	print(data)
	if max < data:
		max = data
	sum = sum + data
print(sum - max//2)
S = input()
T = input()
c = 0
for s,t in zip(S,T):
  if s = t: c+=1
print(c)

### FIXED CODE ###

S = input()
T = input()
c = 0
for s,t in zip(S,T):
  if s == t: c+=1
print(c)
for i in int(input()):
	values = sorted(map(lambda x: int(x)^2, input().split()))
	if values[2] == values[1] + values[0]:
		print 'YES'
	else:
		print 'NO'


### FIXED CODE ###

def judge_triangle(edges):
    edges.sort(reverse = True)
    if edges[0]**2 == edges[1]**2 + edges[2]**2:
        return 'YES'
    else:
        return 'NO'

lines = int(input())

for i in range(lines):
    edges = list(map(int, raw_input().split()))
    print judge_triangle(edges)
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,p = get_nums_l()
s = input()
X = list(map(int, list(s)))
n = len(s)

if p in (2,5):
    ans = 0
    for i,x in enumerate(X):
        if x%p == 0:
            ans += i+1
    print(ans)
else:
    ruiseki = [0] * (n+1)
    for i in (range(n-1, -1, -1)):
        ruiseki[i] = (X[i] * pow(10, (n-i-1), p) + ruiseki[i+1]) % p

    # log(ruiseki)

    ans = 0
    count = defaultdict(int)

    for x in ruiseki:
        # log(count[x])
        ans += count[x]
        count[x] += 1
    # log(count)
    print(ans)



### FIXED CODE ###

import math
from functools import reduce
from collections import deque, defaultdict
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,p = get_nums_l()
s = input()
X = list(map(int, list(s)))
n = len(s)

if p in (2,5):
    ans = 0
    for i,x in enumerate(X):
        if x%p == 0:
            ans += i+1
    print(ans)
else:
    ruiseki = [0] * (n+1)
    for i in (range(n-1, -1, -1)):
        ruiseki[i] = (X[i] * pow(10, (n-i-1), p) + ruiseki[i+1]) % p

    # log(ruiseki)

    ans = 0
    count = defaultdict(int)

    for x in ruiseki:
        # log(count[x])
        ans += count[x]
        count[x] += 1
    # log(count)
    print(ans)
N = int(input())
red = [list(map(int, input().split())) for i in range (N)]
blue = [list(map(int, input().split())) for i in range (N)]
blue.sort(key=lambda x:x[0])
red.sort(key=lambda x:x[1], reverse=True)
pairs = 0
flag = [True for i in range(N)]
for i in range(N):
    for j in range(N):
        if blue[i][0] > red[j][0] and blue[i][1] > red[j][1] and flag[j]:
            pairs += 1
            flag[j] = False
            break
print(pairs)

### FIXED CODE ###

c = [list(map(int, input().split())) for i in range(3)]
a = [0 for i in range(3)]
b = [0 for i in range(3)]
a[0] = 0
a[1] = c[1][1] - c[0][1]
a[2] = c[2][2] - c[0][2]
b[0] = c[0][0]
b[1] = c[0][1]
b[2] = c[0][2]
flag = True
for i in range(3):
    for j in range(3):
        if c[i][j] != a[i] + b[j]:
            flag = False
print("Yes") if flag else print("No")
for i in xrange(1,10):
    for j in xrange(1,10):
        print str(i)+ "x" + str(j) + "=" + str(i*J)

### FIXED CODE ###

for i in xrange(1,10):
    for j in xrange(1,10):
        print str(i)+ "x" + str(j) +  "="  + str(i*j)
N = input()
x = N % 10
#xはNを10で割ったあまり

if x == 2 or x == 4 or x == 5 or x == 7 or x == 9:
    k = 'hon'
elif x == 0 or x == 1 or x == 6 or x == 8:
    k = 'pon'
else:
    k = 'bon'

print(k)

### FIXED CODE ###

N = int(input())
x = N % 10
#xはNを10で割ったあまり

if x == 2 or x == 4 or x == 5 or x == 7 or x == 9:
    k = 'hon'
elif x == 0 or x == 1 or x == 6 or x == 8:
    k = 'pon'
elif x == 3:
    k = 'bon'

print(k)
n, x, t = map(int, input().plist())
print(((math.floot(n/x))+1)*t)

### FIXED CODE ###

n, x, t = map(int, input().split())
if n%x==0:
  print((n//x)*t)
else:
  print( ((n//x)+1)*t )
#ABC118-B

N,M = (int(x) for x in input().split())
food = [0]*M
count = 0
for i in range(N):
    a = list(map(int, input().split()))
    for j in range(1,a[0]+1):
        food[a[j]] = food[a[j]] + 1
for i in range(M):
    if food[i] == N:
        count = count + 1
print(count)

### FIXED CODE ###

N,M = (int(x) for x in input().split())
a = [[int(x) for x in input().split()] for i in range(N)] 
food = [0]*(M+1)
count = 0
for i in range(N):
    for j in range(1,a[i][0]+1):
        food[a[i][j]] = food[a[i][j]] + 1
for i in range(M+1):
    if food[i] == N:
        count = count + 1
print(count)