Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import defaultdict as dd
import queue
import numpy as np
import sys
input = sys.stdin.readline
N, M, K = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(M)]
cd = [tuple(map(int,input().split())) for _ in range(K)]
dic = dd(list)
for (a,b) in ab:
    dic[str(a)].append(b)
    dic[str(b)].append(a)
seen = set()
def BFS(dic,node):
    cc = set()
    q = queue.Queue()
    q.put(node)
    cc.add(node)
    while not q.empty():
        now_node = q.get()
        cc.add(now_node)
        target = set(dic[str(now_node)]) - cc
        for tgt in target:
            q.put(tgt)
    return cc
c_comp=np.zeros((N),dtype='int32')
len_ls = []
var = 1
for i in range(1,N+1):
    if c_comp[i-1] == 0:
        # 連結判定
        tmp = BFS(dic,i)
        c_comp[np.array(list(tmp))-1] = var
        len_ls.append(len(tmp)-1)
        var += 1

for (a,b) in cd:
    if c_comp[a-1] == c_comp[b-1]:
        dic[str(a)].append(b)
        dic[str(b)].append(a)
res = [len_ls[c_comp[i]-1] - len(dic[str(i+1)]) for i in range(N)]
print(*res)


### FIXED CODE ###

from collections import defaultdict as dd
import queue
import sys
input = sys.stdin.readline
N, M, K = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(M)]
cd = [tuple(map(int,input().split())) for _ in range(K)]
dic = dd(list)
for (a,b) in ab:
    dic[str(a)].append(b)
    dic[str(b)].append(a)
uf = [-1]*N
def BFS(ufid, dic, node):
    leng = -1
    q = queue.Queue()
    q.put(node)
    while not q.empty():
        now_node = q.get()
        if uf[now_node-1] > 0:
            continue
        leng += 1
        uf[now_node-1] = ufid
        target = [val for val in dic[str(now_node)] if uf[val-1]==-1]
        for tgt in target:
            q.put(tgt)
            uf[tgt-1] = 0
    return leng

len_ls = []
var = 1
for i in range(N):
    if uf[i] == -1:
        # 連結判定
        leng = BFS(var, dic, i+1)
        len_ls.append(leng)
        var += 1
for (a,b) in cd:
    if uf[a-1] == uf[b-1]:
        dic[str(a)].append(b)
        dic[str(b)].append(a)
res = [len_ls[uf[i]-1] - len(dic[str(i+1)]) for i in range(N)]
print(*res)
### BUGGY CODE ###

def z_algolithm(S, x):
    length = len(S) - x
    A = [0]*length
    i = 1; j = 0
    A[0] = length
    while i < length:
        while i+j < length and S[x+j] == S[x+i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while k < length - i  and k + A[k] < j :
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    ans = 0
    for a in A:
        if a <= length//2:
            ans = max(ans, a)
    return ans

N = int(input())
S = input()
ans = max([z_algolithm(S, x) for x in range(N)])
print(ans)


### FIXED CODE ###

def z_algolithm(S, x):
    length = len(S) - x
    A = [0]*length
    B = [0]
    i = 1; j = 0
    while i < length:
        while i+j < length and S[x+j] == S[x+i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        B.append(min(j, i))
        k = 1
        while k < length - i  and k + A[k] < j :
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    ans = max(B)
    return ans

N = int(input())
S = input()
ans = max([z_algolithm(S, x) for x in range(N)])
print(ans)
### BUGGY CODE ###

N=int(input())
S=[input() for i in range(N)]
dictionary={}
for word in S:
    if word in dictionary:
        dictionary[word]+=1
    else:
        dictionary[word]=1
for key,value in sorted(dictionary.items()):
    if value==max(dictionary.values()):
        print(key)

### FIXED CODE ###

from collections import OrderedDict
N=int(input())
d=dict()
A=[]
ma=0
for i in range(N):
  s=input()
  if s not in d:
    d[s]=0
  d[s]+=1
d=OrderedDict(sorted(d.items(), key=lambda x:x[1], reverse=True))
for i in d:
  if ma<=d[i]:
    ma=d[i]
  if ma!=d[i]:
    break
  A.append(i)
print(*sorted(A),sep="\n")
### BUGGY CODE ###

A,B,C,D = list(map(int,input().split()))

num = 0
for i in range(B-A+1):
  N = A+i
  if (N%C)!=0 and (N%D)!=0:
    num += 1
    
print(num)

### FIXED CODE ###

import fractions

A,B,C,D = list(map(int,input().split()))

G = C*D // fractions.gcd(C,D)

b = B // C + B // D - B // G
am = (A-1) // C + (A-1) // D - (A-1) // G

result = B-A+1-(b-am)
print(result)
### BUGGY CODE ###

from collections import defaultdict
def main():
    N, Q = map(int, input().split())

    # tree = [[] for _ in range(N)]
    tree = defaultdict(list)

    for _ in range(N-1):
        a,b = map(int, input().split())
        a -= 1
        b -= 1
        tree[a].append(b)

    for i in range(N-1,-1,-1):
        if tree[i]:
            for j in tree[i]:
                if tree[j]:
                    for k in tree[j]:
                        tree[i].append(k)
    
    ans = [0] * N

    score = defaultdict(int)
    for _ in range(Q):
        p, x = map(int, input().split())
        p -= 1
        score[p] += x

    for i,j in score.items():
        ans[int(i)] += j
        for k in tree[int(i)]:
            ans[k] += j

    print(*ans)


main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(v, p, tree, ans):
    for u in tree[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v, tree, ans)

def main():
    N, Q = map(int, input().split())
    tree = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        tree[a].append(b)
        tree[b].append(a)
    ans = [0] * N
    for i in range(Q):
        p, x = map(int, input().split())
        p -= 1
        ans[p] += x

    dfs(0, -1, tree, ans)

    print(*ans)

main()
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

for i in range(len(a)):
    tmp_a = a.copy()
    del tmp_a[i]
    print(max(tmp_a))



### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

sorted_a = sorted(a)
first_a = sorted_a[-1]
second_a = sorted_a[-2]

for i in range(len(a)):
    if a[i] == first_a:
        print(second_a)
    else:
        print(first_a)
### BUGGY CODE ###

from collections import deque
from sys import stdin


def main():
    height, width = map(int, stdin.readline().split())
    q = deque([])
    grid = []
    for i in range(height):
        now = list(stdin.readline())
        for j in range(width):
            if now[j] == "#":
                q.append([i, j, 0])
        grid.append(now)
    d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    answer = 0
    while q:
        y, x, time = q.popleft()
        answer = max(answer, time)
        for dy, dx in d:
            new_y = y + dy
            new_x = x + dx
            if 0 <= new_y < height and 0 <= new_x < width and grid[new_y][new_x] == ".":
                grid[new_y][new_x] = "#"
                q.append([new_y, new_x, time + 1])
    print(answer)


if __name__ == '__main__':
    main()



### FIXED CODE ###

from collections import deque
from sys import stdin


def main():
    height, width = map(int, stdin.readline().split())
    q = deque([])
    grid = [stdin.readline() for _ in range(height)]
    distance = [[-1 for _ in range(width)] for _ in range(height)]
    for i in range(height):
        for j in range(width):
            if grid[i][j] == "#":
                q.append((i, j))
                distance[i][j] = 0
    answer = 0
    delta = ((0, 1), (1, 0), (0, -1), (-1, 0))
    while q:
        y, x = q.popleft()
        answer = distance[y][x]
        for dy, dx in delta:
            new_y = y + dy
            new_x = x + dx
            if 0 <= new_y < height and 0 <= new_x < width and distance[new_y][new_x] < 0:
                distance[new_y][new_x] = answer + 1
                q.append((new_y, new_x))
    print(answer)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n=INT()
    dic=[]
    ct=[0]*n
    for i in range(n):
        s=STR()
        if s in dic:
            t=dic.index(s)
            ct[t]+=1
        else:
            dic.append(s)
            ct[len(dic)-1]+=1

    mct=max(ct)
    ans=[]
    for i in range(n):
        if ct[i]==mct:
            ans.append(dic[i])

    ans=sorted(ans)

    for i in ans:
        print(i)

if __name__=='__main__':
    do()

### FIXED CODE ###

from collections import Counter as Ct
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n=INT()
    dic=[]
    for i in range(n):
        s=STR()
        dic.append(s)
    ctd=Ct(dic)
    ctm=max(ctd.values())
    ans=[]
    for key,value in ctd.items():
        if value==ctm:
            ans.append(key)
    
    ans=sorted(ans)

    for i in ans:
        print(i)


if __name__=='__main__':
    do()
### BUGGY CODE ###

A, B, C, K = map(int, input().split())
Maxpos = 0
List = []
for i in range(A):
    List.append(1)
for i in range(B):
    List.append(0)
for i in range(C):
    List.append(-1)
for i in range(K):
    Maxpos += List[i]
print(Maxpos)

### FIXED CODE ###

a, b, c, k = map(int, input().split())
if k > a:
    af = k - a
    ab = abs(af-b)
    print(a-ab)
else:
    print(k)
### BUGGY CODE ###

n=int(input())
ans=1
num= list(map(int,input().split()))
for i in num:
  ans*=i
  if ans>1000000000000000000:
    ans*=-1

if ans<0:
  ans=-1
print(ans)

### FIXED CODE ###

n=int(input())
ans=1
zero=False
minus=False
li = input().split()
for i in li:
  a=int(i)
  if a==0:
    zero=True
    break
  if minus:
    continue
  ans*=a
  if ans>1000000000000000000:
    minus=True

if minus:
  ans=-1
if zero:
  ans=0
print(ans)
### BUGGY CODE ###

from operator import itemgetter

N, T = [int(i) for i in input().split()]

data = []
for i in range(N):
    data.append([int(i) for i in input().split()])

data.sort(key=itemgetter(0))

dp = [[0] * (T+1) for i in range(N)]

dp[0][T] = data[0][1]
for i in range(1, N):
    time = data[i-1][0]
    value = data[i-1][1]
    add_value = data[i][1]
    for j in range(T):
        if j >= time:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-time] + value)
        else:
            dp[i][j] = dp[i-1][j]
    dp[i][T] = dp[i][T-1] + add_value

ans = max([row[-1] for row in dp[:]])
print(ans)


### FIXED CODE ###

from operator import itemgetter
N, T = [int(i) for i in input().split()]

data = []
for i in range(N):
    data.append([int(i) for i in input().split()])

data.sort(key=itemgetter(0))

dp = [[0]*(T) for i in range(N)]
ans = data[0][1]
for i in range(1, N):
    for j in range(T):
        if j >= data[i-1][0]:
            value1 = dp[i-1][j]
            value2 = dp[i-1][j-data[i-1][0]] + data[i-1][1]
            dp[i][j] = max(value1, value2)
        else:
            dp[i][j] = dp[i-1][j]
    value3 = dp[i][T-1] + data[i][1]
    ans = max(value3, ans)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

n = int(input())
a = [int(i) for i in input().split()]

k = [0] * 60

for i in a:
    for j in range(60):
        if (i >> j) & 1:
            k[j] += 1

ans = 0
c = 0
for d in k:
    ans += (d * (n - d) * 2**c)  % (10**9 + 7)
    c += 1
    
print(ans % (10**9 + 7))

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import numpy as np

n = int(input())
a = np.array([int(i) for i in input().split()])

k = [0] * 60

for j in range(60):
    l = a & 1
    k[j] = np.count_nonzero(l)
    a >>= 1

ans = 0
c = 0
for d in k:
    ans += (d * (n - d) * 2**c)  % (10**9 + 7)
    c += 1
    
print(ans % (10**9 + 7))
### BUGGY CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
C = collections.Counter(A)

ans = {}
key = C.keys()
val = C.values()
key = list(key)
val = list(val)

for i in range(len(key)):
    ans[key[i]] = val[i] * (val[i]-1) //2

ans_key = [ans.keys()]
ans_val = list(ans.values())
ans_val = [int(_) for _ in ans_val]

for j in range(N):
    print(sum(ans_val) - (C[A[j]] - 1) )


### FIXED CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
C = collections.Counter(A)

ans = 0
for i in C.values():
    ans += int(0.5* i * (i-1))
for j in A:
    print(ans-C[j]+1)
### BUGGY CODE ###

a, b, n = map(int, input().split())
ans = [int(a * x / b) - a * int(x / b) for x in range(n+1)]
print(max(ans))


### FIXED CODE ###

A, B, N = map(int, input().split())

x = min(B-1, N)
print(A*x // B - A * (x//B))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, M = mi()
#Q = li2(M)

#Q = sorted(Q, key=lambda x:x[0])

table = dp2(0, N, N)

for i in range(M):
    s, t = mi()
    table[s-1][t-1] = 1

for i in reversed(range(N-1)):
    for j in range(i, N):
        table[i][j] = max(table[i+1][j], table[i][j])

#print(table)

i = j = 0
cnt = 0
while True:
    while j < N and table[i][j] == 0:
        j += 1
    if j >= N:
        break
    cnt += 1
    i = j

print(cnt)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, M = mi()
Q = li2(M)
#Q = sorted(Q, key=lambda x:x[1])

l = [N]*N
for i in range(M):
    ind = max(0, Q[i][0]-1)
    l[ind] = min(Q[i][1]-1, l[ind])

for i in reversed(range(N-1)):
    l[i] = min(l[i], l[i+1])

cnt = 0
i = 0
#print(l)
while True:
    i = l[i]
    cnt += 1
    if l[i] == N:
        break

print(cnt)
### BUGGY CODE ###

import time
s_time = time.time()


n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

memo = {}
for i in range(n):
    memo[i] = 0

cnt = 0
while True:
    visited = [False] * n
    flag = False
    for i in range(n):
        if memo[i] == len(a[0]):
            continue
        if visited[i] or visited[a[i][memo[i]] - 1]:
            continue
        visited[i] = True
        if i + 1 == a[a[i][memo[i]] - 1][memo[a[i][memo[i]] - 1]]:
            visited[a[i][memo[i]] - 1] = True
            flag = True
            tmp = memo[i]
            memo[i] += 1
            memo[a[i][tmp] - 1] += 1
    if flag:
        cnt += 1
    else:
        for i in memo:
            if memo[i] != len(a[0]):
                print(-1)
                exit()
        break
    if abs(s_time - time.time()) > 1.7:
        print(n*(n-1) //2)
print(cnt)


### FIXED CODE ###

import time
s_time = time.time()


n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

memo = {}
for i in range(n):
    memo[i] = 0

cnt = 0
while True:
    visited = [False] * n
    flag = False
    for i in range(n):
        if memo[i] == len(a[0]):
            continue
        if visited[i] or visited[a[i][memo[i]] - 1]:
            continue
        visited[i] = True
        if i + 1 == a[a[i][memo[i]] - 1][memo[a[i][memo[i]] - 1]]:
            visited[a[i][memo[i]] - 1] = True
            flag = True
            tmp = memo[i]
            memo[i] += 1
            memo[a[i][tmp] - 1] += 1
    if flag:
        cnt += 1
    else:
        for i in memo:
            if memo[i] != len(a[0]):
                print(-1)
                exit()
        break
    if abs(s_time - time.time()) > 1.7:
        print(n*(n-1) //2)
        exit()
print(cnt)
### BUGGY CODE ###

import numpy as np

H, W = map(int, input().split())
obs = [[False for _ in range(W)] for _ in range(H)]
for y in range(H):
    s = input()
    for x in range(W):
        obs[y][x] = (s[x] == '#')

inc_x = [[0 for _ in range(W)] for _ in range(H)]
cnt_x = [[0 for _ in range(W)] for _ in range(H)]
for y in range(H):
    for x in range(W):
        if obs[y][x]: 
            inc_x[y][x]= 0
        elif x == 0 or obs[y][x-1]:
            inc_x[y][x] = 1
        else:
            inc_x[y][x] = inc_x[y][x-1] + 1
    for x in reversed(range(W)):
        if obs[y][x]:
            cnt_x[y][x]= 0
        elif x == W-1 or obs[y][x+1]:
            cnt_x[y][x] = inc_x[y][x]
        else:
            cnt_x[y][x] += cnt_x[y][x+1]

inc_y = [[0 for _ in range(W)] for _ in range(H)]
cnt_y = [[0 for _ in range(W)] for _ in range(H)]
for x in range(W):
    for y in range(H):
        if obs[y][x]: 
            inc_y[y][x]= 0
        elif y == 0 or obs[y-1][x]:
            inc_y[y][x] = 1
        else:
            inc_y[y][x] = inc_y[y-1][x] + 1
    for y in reversed(range(H)):
        if obs[y][x]:
            cnt_y[y][x]= 0
        elif y == H-1 or obs[y+1][x]:
            cnt_y[y][x] = inc_y[y][x]
        else:
            cnt_y[y][x] += cnt_y[y+1][x]


cnt = np.amax(np.array([[cnt_x[y][x]+cnt_y[y][x] for x in range(W)] for y in range(H)])) - 1
print(cnt)


### FIXED CODE ###

H, W = map(int, input().split())
obs = [[False for _ in range(W)] for _ in range(H)]
for y in range(H):
    s = input()
    for x in range(W):
        obs[y][x] = (s[x] == '#')

inc_x = [[0 for _ in range(W)] for _ in range(H)]
cnt_x = [[0 for _ in range(W)] for _ in range(H)]
for y in range(H):
    for x in range(W):
        if obs[y][x]: 
            inc_x[y][x]= 0
        elif x == 0 or obs[y][x-1]:
            inc_x[y][x] = 1
        else:
            inc_x[y][x] = inc_x[y][x-1] + 1
    for x in reversed(range(W)):
        if obs[y][x]:
            cnt_x[y][x]= 0
        elif x == W-1 or obs[y][x+1]:
            cnt_x[y][x] = inc_x[y][x]
        else:
            cnt_x[y][x] += cnt_x[y][x+1]

inc_y = [[0 for _ in range(W)] for _ in range(H)]
cnt_y = [[0 for _ in range(W)] for _ in range(H)]
for x in range(W):
    for y in range(H):
        if obs[y][x]: 
            inc_y[y][x]= 0
        elif y == 0 or obs[y-1][x]:
            inc_y[y][x] = 1
        else:
            inc_y[y][x] = inc_y[y-1][x] + 1
    for y in reversed(range(H)):
        if obs[y][x]:
            cnt_y[y][x]= 0
        elif y == H-1 or obs[y+1][x]:
            cnt_y[y][x] = inc_y[y][x]
        else:
            cnt_y[y][x] += cnt_y[y+1][x]


cnt = [[cnt_x[y][x]+cnt_y[y][x]-1 for x in range(W)] for y in range(H)]
ans = max([max(cnt[y]) for y in range(H)])
print(ans)
### BUGGY CODE ###

N = int(input())
A = input().split()
A = [int(s) for s in A]
A_sort = sorted(A)
for a_sort in A_sort:
    for i, a in enumerate(A):
        if a_sort == a:
            print(i+1)
            break
    

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
L = [[] for i in range(N)]
for i in range(N):
    L[i] = [A[i], i+1]
L = sorted(L)
for i in range(N):
    print(L[i][1])
### BUGGY CODE ###

N,M=map(int,input().split())

for i in range(N,M+1):
    if M%i==0:
        print(M//i)
        exit()

### FIXED CODE ###

N,M=map(int,input().split())
if N==1:
    print(M)
    exit()

if N>=M**0.5:
    for i in range(M//N,0,-1):
        if M%i==0:
            print(i)
            exit()
else:
    for i in range(N,M+1):
        if M%i==0:
            print(M//i)
            exit()
print(1)
### BUGGY CODE ###

a, b, x = map(int, input().split())
int_list = [i for i in range(a, b + 1)]
counter = 0
for i in range(len(int_list)):
    if int_list[i] % x == 0:
        counter += 1

print(counter)


### FIXED CODE ###

a, b, x = map(int, input().split())
print(b // x - (a - 1) // x)
### BUGGY CODE ###

# ほぼ解説AC
# n,m<2000
# len(s),len(t)<100000
import sys

input = sys.stdin.buffer.readline

n, m = map(int, input().split())
mod = 10 ** 9 + 7
S = list(map(int, input().split()))
T = list(map(int, input().split()))


dp = [[0] * (m + 2) for _ in range(n + 2)]
sum_dp = [[0] * (m + 2) for _ in range(n + 2)]
# 空集合も要素とみなすのでdp[0][0]は1
dp[0][0] = 0
# i,jを見る時にi,jまでの累積和がほすぃ。
# i,jを見てi+1,j+1を決める。
for i in range(n + 1):
    for j in range(m + 1):
        # 二次元累積和の計算
        sum_dp[i][j] += dp[i][j]
        if i - 1 >= 0:
            sum_dp[i][j] += sum_dp[i - 1][j]
        if j - 1 >= 0:
            sum_dp[i][j] += sum_dp[i][j - 1]
        if i - 1 >= 0 and j - 1 >= 0:
            sum_dp[i][j] -= sum_dp[i - 1][j - 1]
        sum_dp[i][j] %= mod
        if i < n and j < m:
            # 先にsum_dp[i][j]は計算されていないとだめ。↑
            # i-1字目、j-1字目まででできるものに、新たに一致したものを加えたもの(sum_dp)と空集合(+1)
            if S[i] == T[j]:
                dp[i + 1][j + 1] = sum_dp[i][j] + 1
                dp[i + 1][j + 1] %= mod
print((sum_dp[n][m] + 1) % mod)



### FIXED CODE ###

# ほぼ解説AC
# n,m<2000
# len(s),len(t)<100000
import sys

input = sys.stdin.buffer.readline

n, m = map(int, input().split())
mod = 10 ** 9 + 7
S = list(map(int, input().split()))
T = list(map(int, input().split()))


dp = [[0] * (m + 2) for _ in range(n + 2)]
sum_dp = [[0] * (m + 2) for _ in range(n + 2)]
# 空集合も要素とみなすのでdp[0][0]は1
dp[0][0] = 0
# i,jを見る時にi,jまでの累積和がほすぃ。
# i,jを見てi+1,j+1を決める。
for i in range(n + 1):
    for j in range(m + 1):
        # 二次元累積和の計算
        sum_dp[i][j] += dp[i][j]
        if i - 1 >= 0:
            sum_dp[i][j] += sum_dp[i - 1][j]
        if j - 1 >= 0:
            sum_dp[i][j] += sum_dp[i][j - 1]
        if i - 1 >= 0 and j - 1 >= 0:
            sum_dp[i][j] -= sum_dp[i - 1][j - 1]
        sum_dp[i][j] %= mod
        if i < n and j < m:
            # 先にsum_dp[i][j]は計算されていないとだめ。↑
            # i-1字目、j-1字目まででできるものに、新たに一致したものを加えたもの(sum_dp)と空集合(+1)
            if S[i] == T[j]:
                dp[i + 1][j + 1] = sum_dp[i][j] + 1
                dp[i + 1][j + 1] %= mod
print((sum_dp[n][m] + 1) % mod)
### BUGGY CODE ###

def main():
	n,p = map(int,input().split())
	s = [int(c) for c in list(input().strip())][::-1]
	num = 0
	ans = 0
	if p == 2 or p == 5:
		for i in range(n):
			if s[i]%p == 0:
				ans += n-i
		print(ans)
		return
	arr = [0]*p
	arr[0]=1
	z = 1
	t = 0
	for ss in s:
		t = (t + z*ss)%p	
		z *=10 %p
		arr[t] += 1
	for l in arr:
		ans += l * (l - 1) // 2
	print(ans)
if __name__ == '__main__':
	main()


### FIXED CODE ###

def main():
	N,P = map(int,input().split())
	S = [int(s) for s in list(input().strip())][::-1]
	num = 0
	ans = 0
	if P == 2 or P == 5:
		for i in range(N):
			if S[i]%P == 0:
				ans += N-i
		print(ans)
		return
	L = [0]*P
	L[0]=1
	t = 0
	s = 1
	for z in S:
		t = (z*s+t)%P	
		L[t]+=1
		s=s*10%P
	for l in L:
		ans += l * (l - 1) // 2
	print(ans)

if __name__ == '__main__':
	main()