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

N, M = [ int(it) for it in input().split() ]
MOD = 1000000007

import math
sM = int(math.sqrt(M)+1)

p_li = []
m = M
for i in range(sM):
  for j in range(2,sM+1):
    if (m%j)==0:
      p_li.append(j)
      m//=j
      break
  if (m==1):
    break
if (m!=1):
  p_li.append(m)
    
    
import collections
co = collections.Counter(p_li)
vec = co.values()

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

s = 1
for v in vec:
  X=N-1+v
  Y=N-1
  if (X-Y<Y):
    Y=X-Y
  ss = 1
  for i in range(X,X-Y,-1):
    ss = (ss*i)%MOD
  for i in range(Y,0,-1):
    ss = (ss*mod_inv(i,MOD))%MOD
  s = (s*ss)%MOD
print (s%MOD)
      




### FIXED CODE ###

N, M = [ int(it) for it in input().split() ]
MOD = 1000000007

import math
sM = int(math.sqrt(M)+1)

p_li = []
m = M
for j in range(2,sM+1):
  for i in range(sM):
    if (m%j)==0:
      p_li.append(j)
      m//=j
    else:
      break
  if (m==1):
    break
if (m!=1):
  p_li.append(m)
    
    
import collections
co = collections.Counter(p_li)
vec = co.values()

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

s = 1
for v in vec:
  X=N-1+v
  Y=N-1
  if (X-Y<Y):
    Y=X-Y
  ss = 1
  sd = 1
  for i in range(X,X-Y,-1):
    ss = (ss*i)%MOD
  for i in range(Y,0,-1):
    sd = (sd*i)%MOD
  
  ss = (ss*mod_inv(sd,MOD))%MOD
  s = (s*ss)%MOD
print (s%MOD)
### BUGGY CODE ###

import math
def main():
    N=input()
    S=input()
    N=int(N)
    ans=0
    ind=[]
    tmp={"R":0,"G":0,"B":0}
    for i in S:
        tmp[i]+=1
        ind.append(tmp.copy())
    for i in range(0,N-2):
        for j in range(i+1,N-1):
            if S[i]==S[j]:
                continue
            col=[k for k in ["R","G","B"] if k!=S[i] and k!=S[j]]
            col=col[-1]
            if 2*j-i <N and S[j+j-i]==col:
                ans-=1
            ans+=(ind[-1][col]-ind[j][col])
    print(ans)

main()


### FIXED CODE ###

N=input()
S=input()
N=int(N)
ans=0
ind=[]
tmp={"R":0,"G":0,"B":0}
for i in S:
    tmp[i]+=1
    ind.append(tmp.copy())
#print(ind)
for i in range(0,N-2):
    for j in range(i+1,N-1):
        if S[i]==S[j]:
            continue
        for k in tmp.keys():
            if k!=S[i] and k!=S[j]:
                col=k
                break
        #print(i,j,col)
        if 2*j-i <N and S[j+j-i]==col:
            ans-=1
        ans+=(ind[-1][col]-ind[j][col])
print(ans)
### BUGGY CODE ###

#横にn個入力
n, m, q = map(int, input().split())
#行列
s = []
for i in range(m):#h:高さ
    s.append([int(m) for m in input().split()] + [i])
# 行列
t = []
for i in range(q):  # h:高さ
    t.append([int(m) for m in input().split()])

LR = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for v in range(m):
     LR[s[v][0]][s[v][1]] += 1
for j in range(1, n + 1):
    for i in range(1, n + 1):#Lについての累積和
        LR[i][j] += LR[i - 1][j]

for k in range(q):
    tmp = 0
    for j in range(t[k][0], t[k][1] + 1):#Rについてみていく
        tmp += LR[t[k][1]][j] - LR[t[k][0] - 1][j]

    print(tmp)

### FIXED CODE ###

#横にn個入力
n, m, q = map(int, input().split())
#行列
s = []
for i in range(m):#h:高さ
    s.append([int(m) for m in input().split()] + [i])
# 行列
t = []
for i in range(q):  # h:高さ
    t.append([int(m) for m in input().split()])

LR = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for v in range(m):
     LR[s[v][0]][s[v][1]] += 1

for j in range(1, n + 1):
    for i in range(1, n + 1):#Lについての累積和
        LR[i][j] += LR[i - 1][j]
for i in range(1, n + 1):
    for j in range(1, n + 1):#Rについての累積和，2次元累積和にする
        LR[i][j] += LR[i][j - 1]

for k in range(q):
    tmp = 0
    #for j in range(t[k][0], t[k][1] + 1):#Rについてみていく
        #tmp += LR[t[k][1]][j] - LR[t[k][0] - 1][j]
    tmp += (LR[t[k][1]][t[k][1]] - LR[t[k][1]][t[k][0] - 1]) - (LR[t[k][0] - 1][t[k][1]] - LR[t[k][0] - 1][t[k][0] - 1])

    print(tmp)
### BUGGY CODE ###

n=int(input())
s=input()
ans=3*10^5
for i in range(n):
  ans=min(ans, s[:i].count("W")+s[i+1:].count("E"))
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
cntW = 0
cntE = s[1:].count("E")
ans = cntE
for i in range(1, n):
  if s[i-1] == "W":
    cntW+=1
  if s[i]=="E":
    cntE-=1
  ans=min(ans, cntE+cntW)
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
from collections import deque
a = []
for _ in range(n):
    a.append(list(input()))

count = 0
for x in a:
    count += x.count("#")
#print(count)

b = [[100000 for i in range(m)] for i in range(n)]
#print(a)

x = [0, 0, -1, 1]
y = [-1, 1, 0, 0]

queue = deque([])
now = [0,0]
b[0][0] = 1
while now != [n-1, m-1]:
    for i in range(4):
        if now[0] + y[i] < 0 or now[0] + y[i] >= n or now[1] + x[i] < 0 or now[1] + x[i] >= m:
            continue
        if a[now[0]+y[i]][now[1]+x[i]] == '.':
            queue.append([now[0]+y[i],now[1]+x[i]])
            b[now[0]+y[i]][now[1]+x[i]] = min(b[now[0]][now[1]] + 1, b[now[0]+y[i]][now[1]+x[i]])
    a[now[0]][now[1]] = "#"
    
    if queue == deque([]):
        print(-1)
        exit()
    now = queue.popleft()


ans = n * m - (b[n-1][m-1] + count)
print(ans)



### FIXED CODE ###

n,m = map(int,input().split())
from collections import deque
a = []
for _ in range(n):
    a.append(list(input()))

count = 0
for x in a:
    count += x.count("#")
#print(count)

b = [[-1 for i in range(m)] for i in range(n)]
#print(a)

x = [0, 0, -1, 1]
y = [-1, 1, 0, 0]
queue = deque([[0,0]])
b[0][0] = 1
while queue:
    now = queue.popleft()
    if now == [n-1,m-1]:
        print(n * m - (b[n-1][m-1] + count))
        exit()
    a[now[0]][now[1]] = "#"
    for i in range(4):
        if 0 <= now[0] + y[i] < n and 0 <= now[1] + x[i] < m and b[now[0]+y[i]][now[1]+x[i]] == -1:
            if a[now[0]+y[i]][now[1]+x[i]] == '.':
                queue.append([now[0]+y[i],now[1]+x[i]])
                b[now[0]+y[i]][now[1]+x[i]] = b[now[0]][now[1]] + 1

print(-1)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce

# 最小公倍数を求める
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(numbers):
    return reduce(lcm_base, numbers, 1)

BASE = 10**9 + 7

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

num = lcm(A)
ans = 0
for i in range(N):
    ans += num // A[i]
    ans %= BASE

print(ans)

### FIXED CODE ###

from fractions import gcd
from functools import reduce

# 最小公倍数を求める
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(numbers):
    return reduce(lcm_base, numbers, 1)

BASE = 10**9 + 7

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

num = lcm(A)
ans = 0
for i in range(N):
    ans += num // A[i]
    # ans %= BASE

print(ans%BASE)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))

    sum=[0]*n
    sum[0]=a[0]
    for i in range(1,n):
        sum[i]=sum[i-1]*a[i]
        if i>=k:
            sum[i]/=a[i-k]
    
    # p=[0]*n
    # for i in range(k-1,n):
    #     if i==k-1:
    #         p[i]=sum[i]
    #     else:
    #         p[i]=sum[i]/sum[i-k]


    # for i in range(k,n):
    #     if p[i]>p[i-1]:
    #         print('Yes')
    #     else:
    #         print('No')

    for i in range(k,n):
        if sum[i]>sum[i-1]:
            print('Yes')
        else:
            print('No')


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

for i in range(k,n):
    if a[i]>a[i-k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n,q=map(int,input().split())
ab=[list(map(lambda x:int(x)-1,input().split())) for _ in [0]*(n-1)]
pq=[list(map(int,input().split())) for _ in [0]*q]
for i in range(q):
    pq[i][0]-=1

graph=[[] for _ in [0]*n]
[graph[a].append(b) for a,b in ab if a<b]
[graph[b].append(a) for a,b in ab if a>b]

plus=[0 for _ in [0]*n]
for i,j in pq:
    plus[i]+=j

pos=[]
ans=[0 for _ in [0]*n]
temp=0
q=[0]
memo=[False for _ in [0]*n]

while q:
    i=q.pop(-1)
    if memo[i]==False:
        pos.append(i)
        temp+=plus[i]
        ans[i]=temp
    memo[i]=True

    while graph[i]:
        j=graph[i].pop(-1)
        if memo[j]==False:
            q.append(j)
            break
    else:
        temp-=plus[pos[-1]]
        pos.pop(-1)
        if pos!=[]:
            q.append(pos[-1])
print(*ans)

### FIXED CODE ###

n,q=map(int,input().split())
ab=[list(map(lambda x:int(x)-1,input().split())) for _ in [0]*(n-1)]
pq=[list(map(int,input().split())) for _ in [0]*q]
for i in range(q):
    pq[i][0]-=1

graph=[[] for _ in [0]*n]
[graph[a].append(b) for a,b in ab if a<b]
[graph[b].append(a) for a,b in ab if a>b]

plus=[0 for _ in [0]*n]
for i,j in pq:
    plus[i]+=j

pos=[]
ans=[0 for _ in [0]*n]
temp=0
q=[0]
memo=[False for _ in [0]*n]

while q:
    i=q.pop(-1)
    if memo[i]==False:
        pos.append(i)
        temp+=plus[i]
        ans[i]=temp
    memo[i]=True

    while graph[i]:
        j=graph[i].pop(-1)
        if memo[j]==False:
            q.append(j)
            break
    else:
        temp-=plus[pos[-1]]
        pos.pop(-1)
        if pos!=[]:
            q.append(pos[-1])
print(*ans)
### BUGGY CODE ###

n=int(input())
s=list(map(int,input().split()))
a=[0]
for _ in range(n):
    a.append(sum(s[:_+1]))

ans=10**9
f=1
g=3
for i in range(2,n-1):
    while f < i and abs(a[f]-(a[i]-a[f])) > abs(a[f+1]-(a[i]-a[f+1])):
        f+=1
    while g < n and abs(a[g]-a[i]-(a[n]-a[g])) > abs(a[g+1]-a[i]-(a[n]-a[g+1])):
        g+=1
    ls=[a[f],a[i]-a[f],a[g]-a[i],a[n]-a[g]]
    ans=min(ans,max(ls)-min(ls))
print(ans)

### FIXED CODE ###

n=int(input())
s=list(map(int,input().split()))
a=[0]
c=0
for si in s:
    c+=si
    a.append(c)
ans=[]
f=1
g=3
for i in range(2,n-1):
    while abs(a[f]-(a[i]-a[f])) > abs(a[f+1]-(a[i]-a[f+1])):
        f+=1
    while abs(a[g]-a[i]-(a[n]-a[g])) > abs(a[g+1]-a[i]-(a[n]-a[g+1])):
        g+=1
    ls=[a[f],a[i]-a[f],a[g]-a[i],a[n]-a[g]]
    ans.append(max(ls)-min(ls))
print(min(ans))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np

n, m = map(int, input().split())
h = np.array(input().split(), dtype='int')
good_tower = np.arange(1, n+1)
bad_tower = np.zeros((), dtype='int')

for i in range(m):
    way = np.array(input().split(), dtype='int')

    if h[way[0]-1] > h[way[1]-1]:
        bad_tower = np.append(bad_tower, way[1])
    elif h[way[0]-1] < h[way[1]-1]:
        bad_tower = np.append(bad_tower, way[0])
    elif h[way[0]-1] == h[way[1]-1]:
        bad_tower = np.append(bad_tower, way[0])
        bad_tower = np.append(bad_tower, way[1])

bad_tower = np.array(list(set(bad_tower)))

ans = len(good_tower) - len(bad_tower) + 1

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

n, m = map(int, input().split())
h = np.array(input().split(), dtype='int')
bad_tower = np.zeros((n), dtype='int')

for i in range(m):
    a, b = map(int, input().split())
    ha = h[a-1]
    hb = h[b-1]

    if ha > hb:
        bad_tower[b-1] = 1
    elif ha < hb:
        bad_tower[a-1] = 1
    elif ha == hb:
        bad_tower[a-1] = 1
        bad_tower[b-1] = 1

ans = n - np.sum(bad_tower)

print(ans)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
cost_1 = 0
cost_2 = 0
cost_3 = 0
cost_4 = 0
S = sum(A)
S_1 = sum(A)
S_2 = sum(A)
S_3 = sum(A)
S_4 = sum(A)
half = S / 2
l = 0
i = 0
while l < half:
    l += A[i]
    i += 1
l_big = l
l_small = l - A[i-1]
if l_big == S - l:
    print(0)
elif l_big - half < half - l_small:
    l_1 = l_big
    l_2 = l_big
    while l_1 > S_1 - l_big:
        l_1 -= 1
        cost_1 += 1
    while l_2 > S_2 - l_big:
        l_2 -= 1
        cost_2 += 1
    print(min(cost_1, cost_2))
else:
    l_3 = l_small
    l_4 = l_small
    while l_3 < S_3 - l_small:
        l_3 += 1
        cost_3 += 1
    while l_4 < S_4 - l_small:
        l_4 += 1
        cost_4 += 1
    print(min(cost_3, cost_4))

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
B = A[::-1]
S = [0] * n
S[0] = A[0]
T = [0] * n
T[0] = B[0]
ans = float('inf')
for i in range(1, n):
    S[i] = S[i - 1] + A[i]
    T[i] = T[i - 1] + B[i]
T = T[::-1]
ans = 2020202020 + 1
for i in range(n):
    diff = abs(S[i] - T[i] - A[i])
    ans = min(ans, diff)
print(ans)
### BUGGY CODE ###

n = int(input())
lst = [int(i) for i in input().split()]
for i in range(n):
    local_lst = lst[:i] + lst[i+1:]
    lst_sort = sorted(local_lst)
    print(lst_sort[n//2-1])

### FIXED CODE ###

n = int(input())
lst = [int(i) for i in input().split()]
lst_sort = sorted(lst)
med = (lst_sort[n//2] + lst_sort[n//2-1])/2

for i in range(n):
    if lst[i] < med:
        print(lst_sort[n//2])
    else:
        print(lst_sort[n//2-1])
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
a = []
for i in range(X):
    for j in range(Y):
        a.append(A[i] + B[j])
a.sort()
b = []
for i in range(min(3000, X * Y)):
    b.append(a[- i - 1])
c = []
for i in range(len(b)):
    for j in range(Z):
        c.append(b[i] + C[j])
c.sort()
for i in range(K):
    print(c[- i - 1])


### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
a = []
for i in range(X):
    for j in range(Y):
        a.append(A[i] + B[j])
a.sort()
b = []
for i in range(min(3000, X * Y)):
    b.append(a[- i - 1])
c = []
for i in range(len(b)):
    for j in range(Z):
        c.append(b[i] + C[j])
c.sort()
for i in range(K):
    print(c[- i - 1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

n = int(input())
a = list(map(int, input().split()))
if n==2:
    print(abs(a[0]-a[1]))
else:
    for i in range(n):
        if sum(a[:i]) > sum(a[i:]):
            print(min(abs(sum(a)-2*sum(a[i-1:])), abs(sum(a)-2*sum(a[i:]))))
            break

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
sum_A = sum(A)
sum_a = 0
ans = 0
if n == 2:
    print(abs(A[0]-A[1]))
else:
    for a in A:
        if (sum_a+a)*2 <= sum_A:
            sum_a += a
        else:
            ans = min(abs(sum_A - 2*sum_a),abs(sum_A - 2*(sum_a+a)))
            print(ans)
            break
### BUGGY CODE ###

n, k = map(int,input().split())
lst = list(map(int,input().split()))

a = [0]*200000
for i in range(200000):
  a[i]=lst.count(i+1)
a.sort()
ans = 0
for i in range(k):
  if a[-1] == 0:
    ans = n
  else:
    ans += a[-1]
    del a[-1]
print(n-ans)

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

num = []
cnt = []

for i in range(N):
    if i == 0:
        num.append(A[i])
        cnt.append(1)
    else:
        if A[i-1] != A[i]:
            num.append(A[i])
            cnt.append(1)
        else:
            cnt[-1] += 1
cnt.sort()
#print(num,cnt)

res = 0
M = len(cnt)
if M <= K:
    res = 0
else:
    for i in range(M-K):
        res += cnt[i]
print(res)
### BUGGY CODE ###

n = int(input())
lis = []
for i in range(n):
    a = int(input())
    if a not in lis:lis.append(a)
    else:lis.remove(a)
print(len(lis))

### FIXED CODE ###

n = int(input())
lis = set()
for i in range(n):
    a = int(input())
    if a not in lis:lis.add(a)
    else:lis.remove(a)
print(len(lis))
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * n

for i in range(1, n):
    hi = h[i]
    dp[i] = min(dp[j] + abs(hi - h[j]) for j in range(max(i - k, 0), i))

print(dp[n-1])


### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * n

for i in range(1, n):
    hi = h[i]
    s = max(i-k,0)
    dp[i] = min(dpj + abs(hi - hj) for dpj, hj in zip(dp[s:i], h[s:i]))
    
print(dp[-1])
### BUGGY CODE ###

s = input()
q = int(input())
X = [list(input().split()) for _ in range(q)]

for x in X:
    if int(x[0]) == 1:
        s = s[::-1]
        continue
    if int(x[1]) == 1:
        s = x[2] +s
    else:
        s = s +x[2]
print(s)

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())

header = []
footer = []
flag = 0
for i in range(q):
    x = list(input().split())
    if int(x[0]) == 1:
        if flag ==0:
            flag = -1
        else:
            flag = 0
        continue
    if int(x[1]) +flag == 1:
        header.append(x[2])
        # s2 = deque(s)
        # # s.insert(0, x[2])
        # s2.appendleft(x[2])
        # s = list(s2)
    else:
        # s.append(x[2])
        footer.append(x[2])
# ans = ''.join(s)
head = ''.join(reversed(header))
ans = head +s + ''.join(footer)
if flag == -1:
    print(ans[::-1])
else:
    print(ans)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
ac = []
ans = []
for i in range(len(s)-1):
    if s[i]=="A":
        if s[i+1]=="C":
            ac.append(i+1)

for i in range(q):
    l,r = map(int,input().split())
    ct = [i for i in ac if i >= l and i+1 <= r] 
    an = len(ct)
    ans.append(an)
#ここから出力
for i in ans:
    print(i)

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
ac = [0 for i in range(n+1)]
ans = []
for i in range(len(s)-1):
    if s[i:i+2]=="AC":
        ac[i+1] = ac[i] + 1
    else:
        ac[i+1] = ac[i]

for i in range(q):
    l,r = map(int,input().split())
    print(ac[r-1]-ac[l-1])
### BUGGY CODE ###

# coding: utf-8
s = input()
k = int(input())
t = []
u = ""
v = []
a = 0

for i in range(k):
    t.append(s)
    
for j in range(len(t)):
    u += str(t[j])

for l in range(len(u)):
    v.append(u[l])
    
v.append("")
v.append("")
    
for m in range(len(v) - 2):
    if v[m] == v[m + 1] and v[m] != v[m - 1]:
        for n in range(len(v) - 1 - m):
            if not v[m] == v[n + m]:
                a += int(n / 2)
                break

print(a)

### FIXED CODE ###

s = list(input())
n = len(s)
k = int(input())
ans = 0
if s.count(s[0]) == n:
    ans = (n * k) // 2
else:
    c = 1
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            c += 1
        else:
            ans += c // 2
            c = 1
    ans += c // 2
    ans *= k
    if s[0] == s[n - 1]:
        c1 = 0
        c2 = 0
        for i in range(n):
            if s[i] == s[0]:
                c1 += 1
            else:
                break
        for i in range(n - 1, -1, -1):
            if s[i] == s[n - 1]:
                c2 += 1
            else:
                break
        if not c1 // 2 + c2 // 2 == (c1 + c2) // 2:
            ans += k
            ans -= 1
print(ans)
### BUGGY CODE ###

N,P=map(int,input().split())
S=input()
ans=0

if P==2 or P==5:
  for i in range(N):
    s=int(S[i])
    if s%P==0:
      ans+=i+1
  print(ans)
  exit()

U=[0]*(N+1)

for i in range(1,N+1):
  s=int(S[-i:])
  U[-(i+1)]+=s%P
  for j in range(1,i+1):
    if (U[-(i+1)]-U[-j])%P==0:
      ans+=1
print(ans)

### FIXED CODE ###

from collections import defaultdict

N,P=map(int,input().split())
S=input()

def solMin():
  dp=[[0]*P for i in range(N+1)]
  
  for i,s in enumerate(map(int,S), start=1):
    dp[i][s%P]+=1
    for p in range(P):
      dp[i][(p*10+s)%P]+=dp[i-1][p]
  
  return sum(dp[i][0] for i in range(N+1))

def solLarge():
  cnt=defaultdict(int)
  ret=0
  now=0
  
  for d,s in enumerate(map(int, S[::-1])):
    now+=pow(10,d,P)*s
    now%=P
    ret+=cnt[(now-P)%P]
    if now==0:
      ret +=1
    cnt[now]+=1
  
  return ret

print(solMin() if P*N<=10**6 else solLarge())
### BUGGY CODE ###

import re
txt = input()
cnt = 0
while True:
    if re.findall('10',txt):
        a = re.subn('10', '', txt)
        txt = a[0]
        cnt += a[1]
    else:
        if re.findall('01', txt):
            a = re.subn('01', '', txt)
            txt = a[0]
            cnt += a[1]
        else:
            break;
print(int(cnt*2))

### FIXED CODE ###

s = input()
print(int(2*min(s.count('0'),s.count('1'))))
### BUGGY CODE ###

n,k = map(int,input().split())
p_ls = list(map(int, input().split()))
e_ls = [0] * n
for i in range(n):
    p = p_ls[i]
    e = (p*(1+p) // 2) / p
    e_ls[i] = e
max_exp = 0
for start in range(n):
    sum_exp = sum(e_ls[start:start+k])
    max_exp = max(max_exp, sum_exp)
print(max_exp)

### FIXED CODE ###

import numpy as np
n,k = map(int,input().split())
p_ls = list(map(int, input().split()))
e_ls = [0] * n
for i in range(n):
    p = p_ls[i]
    e = (p*(1+p) // 2) / p
    e_ls[i] = e
e_csum = list(np.cumsum(e_ls))
max_exp = 0
for start in range(n):
    if start > 0 and start+k-1 < n:
        sum_exp = e_csum[start+k-1] - e_csum[start-1]
    elif start == 0:
        sum_exp = e_csum[start + k - 1]
    max_exp = max(max_exp, sum_exp)
print(max_exp)
### BUGGY CODE ###

H,W = map(int,input().split())
A = [list(map(int,input().split()))for _ in range(H)]
for i in range(H):
    b = list(map(int,input().split()))
    for j in range(W):
        A[i][j] = abs(A[i][j]-b[j])
NUM = 10000
DP = [[[0]*NUM for i in range(W)]for j in range(H)]
DP[0][0][A[0][0]] = 1
i = 0
for j in range(W-1):
    a = A[i][j+1]
    for k in range(NUM):
        if DP[i][j][k] == 1:
            if 0 <= a-k < NUM:
                DP[i][j+1][a-k] = 1
            if 0 <= k-a < NUM:
                DP[i][j+1][k-a] = 1
            if 0 <= k+a < NUM:
                DP[i][j+1][k+a] = 1
j = 0
for i in range(H-1):
    a = A[i+1][j]
    for k in range(NUM):
        if DP[i][j][k] == 1:
            if 0 <= a-k < NUM:
                DP[i+1][j][a-k] = 1
            if 0 <= k-a < NUM:
                DP[i+1][j][k-a] = 1
            if 0 <= k+a < NUM:
                DP[i+1][j][k+a] = 1
for i in range(H-1):
    for j in range(W-1):
        a = A[i+1][j+1]
        for k in range(NUM):
            if DP[i+1][j][k] == 1:
                if 0 <= a-k < NUM:
                    DP[i+1][j+1][a-k] = 1
                if 0 <= k-a < NUM:
                    DP[i+1][j+1][k-a] = 1
                if 0 <= k+a < NUM:
                    DP[i+1][j+1][k+a] = 1
            if DP[i][j+1][k] == 1:
                if 0 <= a-k < NUM:
                    DP[i+1][j+1][a-k] = 1
                if 0 <= k-a < NUM:
                    DP[i+1][j+1][k-a] = 1
                if 0 <= k+a < NUM:
                    DP[i+1][j+1][k+a] = 1

print(DP[-1][-1].index(1))

### FIXED CODE ###

H,W = map(int,input().split())
A = [list(map(int,input().split()))for _ in range(H)]
for i in range(H):
    b = list(map(int,input().split()))
    for j in range(W):
        A[i][j] = abs(A[i][j]-b[j])
NUM = 6400
DP = [[[0]*NUM for i in range(W)]for j in range(H)]
DP[0][0][A[0][0]] = 1
i = 0
for j in range(W-1):
    a = A[i][j+1]
    for k in range(NUM):
        if DP[i][j][k] == 1:
            if 0 <= a-k < NUM:
                DP[i][j+1][a-k] = 1
            if 0 <= k-a < NUM:
                DP[i][j+1][k-a] = 1
            if 0 <= k+a < NUM:
                DP[i][j+1][k+a] = 1
j = 0
for i in range(H-1):
    a = A[i+1][j]
    for k in range(NUM):
        if DP[i][j][k] == 1:
            if 0 <= a-k < NUM:
                DP[i+1][j][a-k] = 1
            if 0 <= k-a < NUM:
                DP[i+1][j][k-a] = 1
            if 0 <= k+a < NUM:
                DP[i+1][j][k+a] = 1
for i in range(H-1):
    for j in range(W-1):
        a = A[i+1][j+1]
        for k in range(NUM):
            if DP[i+1][j][k] == 1:
                if 0 <= a-k < NUM:
                    DP[i+1][j+1][a-k] = 1
                if 0 <= k-a < NUM:
                    DP[i+1][j+1][k-a] = 1
                if 0 <= k+a < NUM:
                    DP[i+1][j+1][k+a] = 1
            if DP[i][j+1][k] == 1:
                if 0 <= a-k < NUM:
                    DP[i+1][j+1][a-k] = 1
                if 0 <= k-a < NUM:
                    DP[i+1][j+1][k-a] = 1
                if 0 <= k+a < NUM:
                    DP[i+1][j+1][k+a] = 1

print(DP[-1][-1].index(1))