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

from collections import deque


def dfs(G, start):
    S = deque()
    S.append(start)
    while len(S) > 0:
        x, parent = S.pop()
        Counter[x] += Counter[parent]
        for g in G[x]:
            if g == parent:
                continue
            S.append((g, x))


N, Q = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N - 1)]
PX = [tuple(map(int, input().split())) for _ in range(Q)]
G = [[] for _ in range(N + 1)]
for a, b in AB:
    G[a].append(b)
    G[b].append(a)

Counter = [0 for _ in range(N + 1)]

for p, x in PX:
    Counter[p] += x

dfs(G, (1, 0))
Counter = [str(a) for a in Counter]
print(" ".join(Counter[1:]))


### FIXED CODE ###

from collections import deque


def dfs(G, start):
    S = deque()
    S.append(start)
    while len(S) > 0:
        x, parent = S.pop()
        Counter[x] += Counter[parent]
        for g in G[x]:
            if g == parent:
                continue
            S.append((g, x))


N, Q = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N - 1)]
PX = [tuple(map(int, input().split())) for _ in range(Q)]
G = [[] for _ in range(N + 1)]
for a, b in AB:
    G[a].append(b)
    G[b].append(a)

Counter = [0 for _ in range(N + 1)]

for p, x in PX:
    Counter[p] += x

dfs(G, (1, 0))
Counter = [str(a) for a in Counter]
print(" ".join(Counter[1:]))
### BUGGY CODE ###

mod = 10 ** 9 + 7
S = input()
abc = 0
bc = 0
c = 0
q = 0

for i in range(len(S)-1, -1, -1):
    if S[i] == 'C':
        c = (3 ** q + c) % mod
    if S[i] == 'B':
        bc = (bc + c) % mod
    if S[i] == 'A':
        abc = (abc + bc) % mod
    if S[i] == '?':
        abc = (abc * 3 + bc) % mod
        bc = (bc * 3 + c) % mod
        c = (c * 3 + 3 ** q) % mod
        q += 1
        
print(abc)

### FIXED CODE ###

S = input()
mod = 10 ** 9 + 7
abc = 0
bc = 0
c = 0
q = 0

for i in S[::-1]:
    if i == 'A':
        abc = (bc + abc) % mod
    if i == 'B':
        bc = (c + bc) % mod
    if i == 'C':
        c = (pow(3, q, mod) + c ) % mod
    if i == '?':
        abc = (abc * 3 + bc) % mod
        bc = (bc * 3 + c) % mod
        c = (pow(3, q, mod) + c * 3) % mod
        q += 1
        
print(int(abc))
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))

count = Counter(a)
for i in a:
  ans = 0
  for k,v in count.items():
    if k == i: v -= 1
    ans += v*(v-1)//2
  print(ans)

### FIXED CODE ###

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

nums = [0]*(n+1)
for i in a:
  nums[i] += 1
  
t = 0
for j in nums:
  t += j*(j-1)//2

for k in a:
  print(t+1-nums[k])
### BUGGY CODE ###

s = input()
l = []
for i in range(len(s)-1, -1, -1):
    if s[i] == 'B':
        l.append(0)
    else:
        l.append(1)
cnt = 0

for j in range(len(s)):
    for i in range(j, len(s) - 1, 2):
        if l[i] == 1 and l[i+1] == 0:
            l[i] = 0
            l[i+1] = 1
            cnt += 1

print(cnt)


### FIXED CODE ###

s = input()

left = 0
ans = 0

for x in s:
    if x == 'B':
        left += 1
        continue
    ans += left

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

import numpy as np
n = int(input())
a = list(map(int, input().split()))

v = np.array(a, dtype=object)
ans = np.prod(v)
if ans > 10**18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
if 0 in a:
  print(0)
  exit()
for i in a:
  ans*=i
  if ans>10**18:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

from scipy.misc import comb


def solve(string):
    n, m, k = map(int, string.split())
    p = 10**9 + 7
    base = n * m * ((n + 1) * (m + 1) * (n + m - 2) - n**2 - m**2 + 2) // 6 % p
    return str(base * (comb(n * m - 2, min(k - 2, n * m - k), exact=True) % p) % p)


if __name__ == '__main__':
    print(solve(input()))


### FIXED CODE ###

mod = 10**9 + 7


def comb(n, k):
    x, y = 1, 1
    k = min(k, n - k)
    for i in range(k):
        x *= n - i
        x %= mod
        y *= i + 1
        y %= mod
    return x * pow(y, mod - 2, mod) % mod


def solve(string):
    n, m, k = map(int, string.split())
    base = n * m * ((n + 1) * (m + 1) * (n + m - 2) - n**2 - m**2 + 2) // 6 % mod
    return str(base * comb(n * m - 2, k - 2) % mod)


if __name__ == '__main__':
    print(solve(input()))
### BUGGY CODE ###

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

for i in range(d):
    t = a.index(max(a))
    a[t] = max(a)//2
    if max(a) == 0:
        break
print(sum(a))

### FIXED CODE ###

import heapq
n, d = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)

for _ in range(d):
    t = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-t//2))

print(-sum(a))
### BUGGY CODE ###

from math import gcd
N = int(input())
A = list(map(int,input().split()))

g = 0
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    exit()

from collections import Counter
def factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d

ctr = Counter()
for a in A:
    fac = factorize(a)
    if fac & ctr:
        print('setwise coprime')
        exit()
    ctr |= fac
print('pairwise coprime')

### FIXED CODE ###

from math import gcd
N = int(input())
A = list(map(int,input().split()))

g = 0
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    exit()

sa = set()
for a in A:
    if a==1: continue
    if a in sa:
        print('setwise coprime')
        exit()
    sa.add(a)

MAXN = 10**6+10
sieve = [0,0] + [1]*MAXN
p = 2
small_primes = []
while p*p <= MAXN:
    if sieve[p]:
        small_primes.append(p)
        for q in range(2*p,MAXN+1,p):
            sieve[q] = 0
    p += 1

st = set()
for a in A:
    for p in small_primes:
        found = False
        while a%p==0:
            a //= p
            found = True
        if found:
            if p in st:
                print('setwise coprime')
                exit()
            st.add(p)
        if a==1: break
    else:
        if a in st:
            print('setwise coprime')
            exit()
        st.add(a)

print('pairwise coprime')
### BUGGY CODE ###

n,m = [int(i) for i in input().split()]
ab = []
for i in range(m):
  ab.append([int(i)-1 for i in input().split()])

def find_index(c,eld):
  if c in eld[c]:
    return(c,len(eld[c]))
  else:
    return(eld[c][0],len(eld[eld[c][0]]))
           
eld = []
for i in range(n):
  eld.append([i])
stat = eld
ans = [int(len(eld)*(len(eld)-1)/2)]

for a,b in ab[1:][::-1]:
#  print(eld)
  a_index,a_size = find_index(a,eld)
  b_index,b_size = find_index(b,eld)
#  print(a_index,b_index)
  if a_index == b_index:
    ans.append(ans[-1])
    continue
  else:
    next = a_size * b_size
    ans.append(ans[-1] - next)

  if a_size >= b_size:
    eld[a_index].extend(eld[b_index])
    for i in eld[a_index][1:]:
      eld[i] = [a_index]
  else:
    eld[b_index].extend(eld[a_index])
    for i in eld[b_index][1:]:
      eld[i] = [b_index]

for i in ans[::-1]:
  print(i)

### FIXED CODE ###

n,m = [int(i) for i in input().split()]
ab = []
for i in range(m):
  ab.append([int(i)-1 for i in input().split()])

def find_index(c,eld):
  if c in eld[c]:
    return(c,len(eld[c]))
  else:
    return(eld[c][0],len(eld[eld[c][0]]))
           
eld = []
for i in range(n):
  eld.append([i])
stat = eld
ans = [int(len(eld)*(len(eld)-1)/2)]

for a,b in ab[1:][::-1]:
#  print(eld)
  a_index,a_size = find_index(a,eld)
  b_index,b_size = find_index(b,eld)
#  print(a_index,b_index)
  if a_index == b_index:
    ans.append(ans[-1])
    continue
  else:
    next = a_size * b_size
    ans.append(ans[-1] - next)

  if a_size >= b_size:
    eld[a_index].extend(eld[b_index])
    for i in eld[b_index]:
      eld[i] = [a_index]
  else:
    eld[b_index].extend(eld[a_index])
    for i in eld[a_index]:
      eld[i] = [b_index]

for i in ans[::-1]:
  print(i)
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
cx, cy = map(lambda x: int(x) - 1, input().split())
dx, dy = map(lambda x: int(x) - 1, input().split())
s = [[i for i in input()] for _ in range(h)]
c = [[10**6] * w for _ in range(h)]

d = ((1, 0), (-1, 0), (0, 1), (0, -1))
q = deque([(cx, cy)])

c[cx][cy] = 0

while q:
    x, y = q.pop()
    cp = c[x][y]
    if (x, y) == (dx, dy):
        c[x][y] = cp
        break
    for i, j in d:
        nx = x + i
        ny = y + j
        if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and c[nx][ny] > cp:
            q.append((nx, ny))
            c[nx][ny] = cp
    cp += 1
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx = x + i
            ny = y + j
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and c[nx][
                    ny] > cp:
                c[nx][ny] = cp
                q.appendleft((nx, ny))
print(-1 * (c[dx][dy] == 10**6) or c[dx][dy])


### FIXED CODE ###

#!/usr/bin/env python3
import heapq

h, w = map(int, input().split())
cx, cy = map(lambda x: int(x) - 1, input().split())
dx, dy = map(lambda x: int(x) - 1, input().split())
s = [input() for _ in range(h)]
c = [[10**6] * w for _ in range(h)]


def bfs():
    d = ((1, 0), (-1, 0), (0, 1), (0, -1))
    d2 = (
        (-2, -2),
        (-2, -1),
        (-2, 0),
        (-2, 1),
        (-2, 2),
        (-1, -2),
        (-1, -1),
        (-1, 1),
        (-1, 2),
        (0, -2),
        (0, 2),
        (1, -2),
        (1, -1),
        (1, 1),
        (1, 2),
        (2, -2),
        (2, -1),
        (2, 0),
        (2, 1),
        (2, 2),
    )
    hp = []

    heapq.heappush(hp, (0, (cx, cy)))
    c[cx][cy] = 0

    while hp:
        cp, (
            x,
            y,
        ) = heapq.heappop(hp)
        if (x, y) == (dx, dy):
            c[x][y] = cp
            break
        for i in range(4):
            nx = x + d[i][0]
            ny = y + d[i][1]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and c[nx][
                    ny] > cp:
                heapq.heappush(hp, (cp, (nx, ny)))
                c[nx][ny] = cp
        cp += 1
        for i in range(20):
            nx = x + d2[i][0]
            ny = y + d2[i][1]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and c[nx][
                    ny] > cp:
                c[nx][ny] = cp
                heapq.heappush(hp, (cp, (nx, ny)))

    return c[dx][dy] if c[dx][dy] < 10**6 else -1


print(bfs())
### BUGGY CODE ###

S = input()
Q = int(input())
Query = [list(map(str, input().split())) for i in range(Q)]

rev_flag = 0

bef = ''
aft = ''

for i in range(Q):
    if Query[i][0] == '1':
        rev_flag = (rev_flag + 1) % 2
    if Query[i][0] == '2':
        if Query[i][1] == '1':
            if rev_flag == 0:
                bef = Query[i][2] + bef
            elif rev_flag == 1:
                aft = aft + Query[i][2]
        elif Query[i][1] == '2':
            if rev_flag == 1:
                bef = Query[i][2] + bef
            elif rev_flag == 0:
                aft = aft + Query[i][2]

S = bef + S + aft
if rev_flag == 1:
    S = S[::-1]

print(S)

### FIXED CODE ###

S = input()
Q = int(input())
Query = [list(map(str, input().split())) for i in range(Q)]

rev_flag = 0

bef = ''
aft = ''

for i in range(Q):
    if Query[i][0] == '1':
        rev_flag = (rev_flag + 1) % 2
    if Query[i][0] == '2':
        if Query[i][1] == '1':
            if rev_flag == 0:
                bef = Query[i][2] + bef
            elif rev_flag == 1:
                aft = aft + Query[i][2]
        elif Query[i][1] == '2':
            if rev_flag == 1:
                bef = Query[i][2] + bef
            elif rev_flag == 0:
                aft = aft + Query[i][2]

S = bef + S + aft
if rev_flag == 1:
    S = S[::-1]

print(S)
### BUGGY CODE ###

s=input()

def sigma(n):
  return n*(n+1)//2

total=0
cnt=0
while s[0]=='>':
  cnt+=1
  s=s[1:]
  if s=='':
    break
total+=sigma(cnt)
  
flag=True
while flag:
  l=[]
  if '>' in s:
    for i in range(s.find('>')):
      l.append(s[i])
    s=s[s.find('>'):]
  else:
    l.extend(['<']*len(s))
    s=''
    flag=False
  if '<' in s:
    for i in range(s.find('<')):
      l.append(s[i])
    s=s[s.find('<'):]
  else:
    l.extend(['>']*len(s))
    s=''
    flag=False
  if l.count('<')<=l.count('>'):
    total+=sigma(l.count('>'))+sigma(l.count('<')-1)
  else:
    total+=sigma(l.count('<'))+sigma(l.count('>')-1)

print(total)

### FIXED CODE ###

s=input()

def sigma(n):
  return n*(n+1)//2

total=0
if s[0]=='>':
  cnt=s.find('<')
  if cnt==-1:
    cnt=len(s)
    s=''
  else:
    s=s[cnt:]
  total+=sigma(cnt)
  
flag=True
while flag:
  l=[]
  index1=s.find('>')
  if index1!=-1:
    for i in range(index1):
      l.append(s[i])
    s=s[index1:]
  else:
    l.extend(['<']*len(s))
    s=''
    flag=False
  index2=s.find('<')
  if index2!=-1:
    for i in range(index2):
      l.append(s[i])
    s=s[index2:]
  else:
    l.extend(['>']*len(s))
    s=''
    flag=False
  cnt1=l.count('>')
  cnt2=l.count('<')
  if cnt2<=cnt1:
    total+=sigma(cnt1)+sigma(cnt2-1)
  else:
    total+=sigma(cnt2)+sigma(cnt1-1)

print(total)
### BUGGY CODE ###

MOD = 1000000007;
 
s = input()
 
n=len(s)
 
if n<1 or n>10**5:
	print ('Illegal')
	exit()
b=[0]*13
pr=[0]*13

p=1

for i in range(n):
	ix=n-1-i
	if(s[ix]=="?"):
		c=-1
	else:
		c=int(s[ix])
	if ( i== 0):
		if (c==-1):
			for j in range(10):
				b[(p*j)%13]=1
		else:
			b[(p*c)%13]=1
	else:
		if (c==-1):
			for j in range(10):
				for k in range(13):
					b[(k+p*j)%13]+=pr[k]
		else:
			for k in range(13):
				b[(k+p*c)%13]+=pr[k]
 
	if (i%30==0 or i==n-1):
		for k in range(13):b[k]%=MOD
	p=p*10%13
#	print (pr)
	for k in range(13):
		pr[k]=b[k]
		b[k]=0
#	print (pr)
print (pr[5])


### FIXED CODE ###

MOD = 1000000007;

s = [int(x) if x!="?" else -1 for x in input()]

n=len(s)

r=[0]*13

c=s[0]
if (c!=-1):
	r[c]=1
else:
	for i in range(10):r[i]=1

for i in range(1,n):
	dp=[0]*26
	for j in range(13):dp[j*10%13]+=(r[j]%MOD)
	dp[13:26]=dp[0:13]
	c=s[i]
	r=[0]*13
	if (c==-1):
		w=sum(dp[4:14])
		for j in range(13):
				r[j]+=w
				w=w+dp[j+1]-dp[4+j]
	else:
		for j in range(13):
			r[j]+=dp[13-c+j]
print (r[5]%MOD)
### BUGGY CODE ###

#from numpy import*
#from scipy import*
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby
from operator import mul
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**6)

def DIJKSTRA(point,d,n):
    cost      = {node:float("inf") for node in range(n)}
    Q         = []  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

def main():
    k=int(input())
    d=defaultdict(list)
    for i in range(k-1): #１加算をつなぐ
        d[i].append([i+1,1])
    d[k-1].append([0,1])
    for i in range(k):  #10倍をつなぐ
        d[i].append([(i*10)%k,0])
    #print(d)
    
    
    print(DIJKSTRA(1,d,k)[0]+1)

    
    
    
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

#from numpy import*
#from scipy import*
from collections import* #defaultdict Counter deque appendleft
#from fractions import gcd
#from functools import* #reduce
#from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby
#from operator import mul
#from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
#from math import factorial
#from copy import deepcopy
import sys
input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**6)

def DIJKSTRA(point,d,n):
    cost      = {node:float("inf") for node in range(n)}
    Q         = []  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

def main():
    k=int(input())
    d=defaultdict(list)
    for i in range(k-1): #１加算をつなぐ
        d[i].append([i+1,1])
    d[k-1].append([0,1])
    for i in range(k):  #10倍をつなぐ
        d[i].append([(i*10)%k,0])
    #print(d)
    
    
    print(DIJKSTRA(1,d,k)[0]+1)

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

MOD = 10 ** 9 + 7
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
dp = [0] * (N + 1)
dp[0] = 1
for i in range(1, N + 1):
    if i in A:
        dp[i] = 0
    else:
        dp[i] = (dp[i - 2] + dp[i - 1]) % MOD
print(dp[N])

### FIXED CODE ###

MOD = 10 ** 9 + 7
N, M = map(int, input().split())
dp = [[0, 0] for _ in range(N + 1)]
dp[0][0] = 1
for _ in range(M):
    x = int(input())
    dp[x][1] = 1
for i in range(1, N + 1):
     if dp[i][1] == 0:
         dp[i][0] = (dp[i - 2][0] + dp[i - 1][0]) % MOD
print(dp[N][0])
### BUGGY CODE ###

n,w = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(n)]
knap = {(0,0)}
for weight,value in lis:
    gone = set()
    for num,now in knap:
        if num + weight <= w:gone.add((num+weight,now+value))
    for nn,nu in gone:
        knap.add((nn,nu))
ans = 0

for num,value in knap:
    ans = max(ans,value)
print(ans)


### FIXED CODE ###

def dp():
    n,w = map(int,input().split())
    lis = (map(int,input().split()) for i in range(n))
    
    dpp = [0] * (w + 1)
    for weight, value in lis:
        for j in range(w,weight-1,-1):
            dp = dpp[j-weight] + value
            if dpp[j] < dp:
                dpp[j] = dp
    return max(dpp)
print(dp())
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
sumans = 0
for i in range(N-1):
    sumans += A[i]*sum(A[i+1:])%mod
    sumans = sumans%mod
print(sumans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
sumpre = 0
sumans = 0
for i in range(N-1):
    sumpre += A[i]
    sumans += A[i+1]*sumpre%mod
    sumans =sumans%mod
print(sumans)
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline

N, K = map(int, input().split())
p = np.array(list(map(int, input().split())))

ans = 0

for i in range(N - K + 1):
    tmp = np.sum(p[i:i + K])
    if ans < tmp:
        ans = tmp

print((ans + K) / 2)


### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline

N, K = map(int, input().split())
p = np.array(list(map(int, input().split())))
c = np.cumsum(p)

ans = c[K-1]

for i in range(N - K):
    tmp = c[i+K] - c[i]
    ans = max(ans, tmp)

print((ans + K) / 2)
### BUGGY CODE ###

import collections
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
lst = []
cnt = [0] * n
ans = 0

for i in range(n):
    s = input()
    c = collections.Counter(s)
    if c not in lst:
        lst.append(c)
    else:
        cnt[lst.index(c)] += 1

for i in cnt:
    if i != 0:
        ans += combinations_count(i+1, 2)
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
count_list = []
for i in range(n):
    s = input()
    c = sorted(Counter(s).items(), key = lambda x:x[0])
    tmp = ""
    for j in range(len(c)):
        tmp += c[j][0]
        tmp += str(c[j][1])
    count_list.append(tmp)

c = Counter(count_list)
ans = 0
for i in c.values():
    if i >= 2:
        ans += i * (i - 1) // 2

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

import numpy as np
S = input()
mod = 10 ** 9 + 7

n = len(S)
dp = np.zeros((n, 13))
a = S[-1]
now, pre = 10, 1
if a == "?":
    dp[0][0:10] = 1
else:
    dp[0][int(a)] = 1
for i, s in zip(range(1, n), reversed(S[:-1])):
    x_ = dp[i - 1]
    x = dp[i]
    if s == "?":
        for v in range(10):
            w = 13 - v * now % 13
            x += np.hstack((x_[w:13], x_[:w]))
            x %= mod
    else:
        v = 13 - int(s) * now % 13
        x += np.hstack((x_[v:13], x_[:v]))
        x %= mod
    now, pre = (now - pre) % 13, now
print(int(dp[-1][5]))

### FIXED CODE ###

#!python3

LI = lambda: list(map(int, input().split()))

# input
S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    l1 = [0] * 13
    l1[0] = 1
    for i in range(1, n + 1):
        l2 = [0] * 13
        for j in range(10):
            x = w[i - 1] * j % 13
            for k in range(13):
                t = (x + k) % 13
                l2[t] += l1[k]
        l1 = [y % MOD for y in l2]
    
    ans = l1[m]
    print(ans)


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

A, B,C,K = map(int, input().split())
ans = 0
for i in range(K):
  if(i+1<=A):
    ans = ans + 1
  elif(i+1<=A+B):
    ans = ans +0
  elif(i+1<=A+B+C):
     ans = ans -1
  #print(ans)
        
        


print(ans)

### FIXED CODE ###

A, B,C,K = map(int, input().split())
if(K<A):
  print(K)
elif(K>A+B):
  print(A - (K-A-B))
else:
  print(A)
### BUGGY CODE ###

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

ans = 0
for i in range(N - K + 1):
    ans = max(ans, sum(p[i:i+K]))

ans = (ans + K) / 2    

print(ans)

### FIXED CODE ###

import numpy as np
from decimal import Decimal

N, K = map(int, input().split())
p = np.array(list(map(int, input().split())))

if N==1:
    print((p.max() + 1) / Decimal(2))
elif N==K:
    print((p.sum() + K) / Decimal(2))
else:
    p = np.cumsum(p)

    ans = []
    for i in range(N - K):
        ans.append(p[i + K]-p[i])

    ans = (max(ans) + K) / Decimal(2)

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

import sys, os
import collections

MOD = 10 ** 9 + 7

def solve(input_stream):
  N, K  = read_ints(input_stream)
  numbers = [int(i) - 1 for i in input_stream.readline().strip().split()]
  cumulative_sum = [0 for i in range(N + 1)]
  mods = [0 for i in range(K)]
  ans = 0
  for index, number in enumerate(numbers):
    cumulative_sum[index + 1] = (cumulative_sum[index] + number) % K
  queue = []
  
  for index in range(N+1):
    ans += mods[cumulative_sum[index]]
    mods[cumulative_sum[index]] += 1
    queue.append(cumulative_sum[index])
    if len(queue) == K:
      target = queue.pop(0)
      mods[target] -= 1
  return [str(ans)]

  


def read_ints(input_stream):
  return [i for i in map(int, input_stream.readline().strip().split())]

def read_int(input_stream):
  return int(input_stream.readline().strip())


if __name__ == "__main__":
    outputs = solve(sys.stdin)
    for line in outputs:
      print(line)

### FIXED CODE ###

import sys, os
import collections

MOD = 10 ** 9 + 7

def solve(input_stream):
  N, K  = read_ints(input_stream)
  numbers = [int(i) - 1 for i in input_stream.readline().strip().split()]
  cumulative_sum = [0 for i in range(N + 1)]
  mods = {}
  ans = 0
  for index, number in enumerate(numbers):
    cumulative_sum[index + 1] = (cumulative_sum[index] + number) % K
  queue = []
  
  for index in range(N+1):
    if cumulative_sum[index] not in mods:
      mods[cumulative_sum[index]] = 0
    ans += mods[cumulative_sum[index]]
    mods[cumulative_sum[index]] += 1
    queue.append(cumulative_sum[index])
    if len(queue) == K:
      target = queue.pop(0)
      mods[target] -= 1
  return [str(ans)]

  


def read_ints(input_stream):
  return [i for i in map(int, input_stream.readline().strip().split())]

def read_int(input_stream):
  return int(input_stream.readline().strip())


if __name__ == "__main__":
    outputs = solve(sys.stdin)
    for line in outputs:
      print(line)