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

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

mmax = 0
idx = 0
for i in range(N-K+1):
  score = sum(P[i:i+K])
  if score > mmax:
    mmax = score
    idx = i
  else:
    continue

print((K+mmax)/2)

### FIXED CODE ###

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

score = sum(P[:K])
mmax = score
idx = 0
for i in range(1, N-K+1):
  score = score - P[i-1] + P[i+K-1]
  if score > mmax:
    mmax = score
    idx = i
  else:
    continue

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

n=int(input())
A=list(map(int,input().split()))
sum=1
f=0
f2=0
for a in A:
	if  (a==0): 
		f2=1
	sum=sum*a
	if (sum>10**18):
		sum=-1
if f2==1: 
	print(0)
else:
	print(sum)

### FIXED CODE ###

N=int(input())
 
A=list(map(int,input().split()))
 
if 0 in A:
    print(0)
else:
    result=1
    for a in A:
        result=result*a
        if result>10**18:
            result=-1
            break
    print(result)
### BUGGY CODE ###

import itertools
N, M, Q = map(int, input().split())
List = [list(map(int, input().split())) for i in range(Q)]
Max = 0

for a in itertools.combinations_with_replacement(range(1, M+1), N):
  A = list(a)
  A.sort()
  point = 0
  for i in range(Q):
    ai = List[i][0]
    bi = List[i][1]
    if 1 <= ai <= N and 1 <= bi <= N:
      if A[bi-1]-A[ai-1] == List[i][2]:
        point += List[i][3]
    if Max < point:
      Max = point

print(Max)


### FIXED CODE ###

import itertools
N, M, Q = map(int, input().split())
List = [list(map(int, input().split())) for i in range(Q)]
Max = 0
 
for a in itertools.combinations_with_replacement(range(1, M+1), N):
  A = list(a)
  A.sort()
  point = 0
  for i in range(Q):
    ai = List[i][0]
    bi = List[i][1]
    if ai < 1 or N < ai or bi < 1 or N < bi:
      continue
    if A[bi-1]-A[ai-1] == List[i][2]:
      point += List[i][3]
  if Max < point:
    Max = point
 
print(Max)
### BUGGY CODE ###

A, B, C, K = map(int, input().split())
res = 0
total = 0
S = K - A
for b in range(B+1):
    for c in range(C+1):
        if S == b + c:
            total = A*1 + b*0 + c*-1
            if res < total:
                res = total
print(res)

### FIXED CODE ###

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

xa = min(A, K)
K = K - xa
xb = min(B, K)
K = K - xb
xc = min(C, K)
total = xa*1 + xb*0 + xc*-1
print(total)
### BUGGY CODE ###

LIM=200002
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
def pop_num2(N,b,L,M):
    if N==0:
        return 0
    v=N%b
    return M[v]+1

M=[0]*200002
for i in range(1,200002):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)+1
c=bin_sum2(Y)-1
for i in range(X):
    Y_i=Y[:i]+str(abs(int(Y[i])-1))+Y[i+1:]
    if Y_i[i]=="1":
        b=d
    else:
        b=c
    print(pop_num2(int(Y_i,2),b,L,M))

### FIXED CODE ###

from collections import deque
LIM=200004
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200005
for i in range(1,200004):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)
e=int(Y,2)%(d+1)
f=int(Y,2)%max(1,(d-1))
O=[1]*(X+2)
P=[1]*(X+2)
q=max(d-1,1)
for i in range(1,X+1):
    O[i]=O[i-1]*2%q
    P[i]=P[i-1]*2%(d+1)
for i in range(X):
    
    if int(Y[i])==1:
        b=max(d-1,1)
        flag=max(0,d-1)
        g=(f-O[X-1-i]+b)%b
    else:
        b=d+1
        flag=1
        g=(e+P[X-1-i])%b

    if flag==0:
        print(0)
    elif g==0:
        print(1)
    else:
        print(M[g]+1)
### BUGGY CODE ###

import math
N=int(input())
for i in range(int(math.sqrt(N)),N+1):
    j=N//i
    if i*j==N:
        print(len(str(i)))
        exit(0)

### FIXED CODE ###

N=int(input())
for i in range(int(N ** 0.5 + 1),-1,-1):
    if N % i == 0:
        print(len(str(N // i)))
        exit(0)
### BUGGY CODE ###

n=int(input())
line=str(input())
line=line.replace('E','0')
line=line.replace('W','1')
line=list(map(int,line))
def turn_e(x):
  count=0
  for i in range(x):
    if line[i]==1:
      count+=1
  return count
def turn_w(x):
  count=0
  for i in range(x+1,n):
    if line[i]==0:
      count+=1
  return count
v=n
for i in range(n):
  if (turn_e(i)+turn_w(i))<v:
    v=turn_e(i)+turn_w(i)
print(v)


### FIXED CODE ###

n=int(input())
s=input()
e=s.count('E')
w=0
ans=e+w
p=0
for i in s:
  if p==1:
    w+=1
    p=0
  if i=='E':
    e-=1
  else:
    p=1
  ans=min(ans,e+w)
print(ans)
### BUGGY CODE ###

s=input()
t=int(input())
u=[input().split()for i in range(t)]
a=0
for i in range(t):
  if u[i][0]=='1':
    s=s[::-1]
  else:
    if u[i][1]=='1':
      s=u[i][2]+s
    else:
      s=s+u[i][2]
print(s)

### FIXED CODE ###

s=input()
t=int(input())
u=[input().split()for i in range(t)]
a=0
b=''
c=''
for i in range(t):
  if u[i][0]=='1':
    a+=1
  else:
    if u[i][1]=='1':
      if a%2==0:
        b=b+u[i][2]
      else:
        c=c+u[i][2]
    else:
      if a%2==0:
        c=c+u[i][2]
      else:
        b=b+u[i][2]
if a%2==0:
  b=b[::-1]
  s=b+s+c
  print(s)
else:
  s=s[::-1]
  c=c[::-1]
  s=c+s+b
  print(s)
### BUGGY CODE ###

import math

(a, b) = tuple([int(s) for s in input().split()])

min = a if a < b else b
divisor = 1

i = 2
while i <= min:
    if a % i == 0 and b % i == 0:
        a = a / i
        b = b / i
        divisor = divisor * i
    else:
        i = i + 1

print(divisor)

### FIXED CODE ###

# 1_1_B

def gcd(x, y):
    while x%y != 0:
        x, y = y, x%y
    return y

x, y = map(int, input().split())
print(gcd(x, y))
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
m = []
for _ in range(3):
    m.append(sorted(list(map(int, input().split())), reverse=True))

def sorted_sum(list_a, list_b):
    s = []
    for x in list_a:
        for y in list_b:
            s.append(x + y)
    return sorted(s, reverse=True)

ans = sorted_sum(sorted_sum(m[0], m[1])[0:k], m[2])
for i in range(0, k):
    print(ans[i])

### FIXED CODE ###

x, y, z, k = map(int, input().split())
m = []
for _ in range(3):
    m.append(sorted(list(map(int, input().split())), reverse=True))

def sorted_sum(list_a, list_b, limit):
    s = []
    for x in list_a:
        for y in list_b:
            s.append(x + y)
    return sorted(s, reverse=True)[0:limit]


def consume_diff(s, a_val, list_b, b_index):
    diff = a_val - list_b[b_index]
    for i in range(b_index + 1, len(list_b)):
        if list_b[b_index] - list_b[i] > diff:
            break
        s.append(a_val + list_b[i])



ans = sorted_sum(sorted_sum(m[0], m[1], k), m[2], k)
for i in range(min([k, len(ans)])):
    print(ans[i])
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    p, z, m = [], 0, []
    for i in range(n):
        t = a[i] - (i + 1)
        if t > 0:
            p.append(t)
        elif t == 0:
            z += 1
        else:
            m.append(-t)
    if sum(m) > sum(p):
        p, m = m[:], p[:]

    ps, ms = sum(p), sum(m)
    pl, ml = len(p), len(m)
    p.sort()
    m.sort()
    x = 0
    ans = ms + ps
    while True:
        if pl <= 0:
            break
        t = p.pop(0)
        t, x = t - x, t
        ps -= pl * t
        pl -= 1
        if t > 0:
            ml += z
            ms += ml * t
            z = 1
        else:
            z += 1
        if ms + ps < ans:
            ans = ms + ps
    print(ans)


main()

### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    p, z, m = [], 0, []
    for i in range(n):
        t = a[i] - (i + 1)
        if t > 0:
            p.append(t)
        elif t == 0:
            z += 1
        else:
            m.append(-t)
    if sum(m) > sum(p):
        p, m = m[:], p[:]

    p.sort()
    ps, ms = sum(p), sum(m)
    pl, ml = len(p), len(m)
    x = 0
    ans = ms + ps
    for t in p:
        t, x = t - x, t
        ps -= pl * t
        pl -= 1
        if t > 0:
            ml += z
            ms += ml * t
            z = 1
            a = ms + ps
            if a < ans:
                ans = a
        else:
            z += 1
    print(ans)


main()
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[]
for i in range(N):
    B.append(A[i])
    B=B[::-1]
print(*B)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
print(*(A[::-2]+A[N%2::2]))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys

# 再帰呼び出しの回数制限(デフォルト1000)
sys.setrecursionlimit(10 ** 9)
 
N, Z, W = map(int, input().split())
aN = list(map(int, input().split()))

def dfs(turn, rest, x, y):
    if rest == 0:
        return abs(x - y)
    if turn % 2 == 0:
        mx = -1
        for i in range(N-rest, N):
            x = aN[i]
            idx = i+1
            mx = max(dfs(turn+1, N-idx, x, y), mx)
        return mx
    else:
        mn = float('inf')
        for i in range(N-rest, N):
            y = aN[i]
            idx = i+1
            mn = min(dfs(turn+1, N-idx, x, y), mn)
        return mn

print(dfs(0, N, Z, W))


### FIXED CODE ###

# -*- coding: utf-8 -*-

"""
参考：https://kimiyuki.net/writeup/algo/atcoder/arc-085-d/
・ミニマックス法
・メモ化再帰
・先手と後手にそれぞれのメモを作る
"""

import sys
from collections import defaultdict

# 再帰呼び出しの回数制限(デフォルト1000)
sys.setrecursionlimit(10 ** 9)
 
N, Z, W = map(int, input().split())
aN = list(map(int, input().split()))

# 先手番用メモ[残り山札数][相手のスコア] = このルートでのmax
# 後手番用メモ[残り山札数][相手のスコア] = このルートでのmin
memo1 = [defaultdict(int) for _ in range(N+1)]
memo2 = [defaultdict(int) for _ in range(N+1)]

def dfs(turn, rest, x, y):
    if rest == 0:
        return abs(x - y)
    # 先手番
    if turn % 2 == 0:
        # 既に見た局面ならメモの内容を返す
        if memo1[rest][y]: 
            return memo1[rest][y]
        mx = -1
        for i in range(N-rest, N):
            x = aN[i]
            idx = i+1
            mx = max(dfs(turn+1, N-idx, x, y), mx)
        # ここより深い所を探し終わったので結果をメモする
        memo1[rest][y] = mx
        return mx
    # 後手番
    else:
        if memo2[rest][x]: 
            return memo2[rest][x]
        mn = float('inf')
        for i in range(N-rest, N):
            y = aN[i]
            idx = i+1
            mn = min(dfs(turn+1, N-idx, x, y), mn)
        memo2[rest][x] = mn
        return mn

print(dfs(0, N, Z, W))
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 998244353

def solve():
    n,s = LI()
    a = LI()
    dp = [[0]*(n+1) for i in range(s+1)]
    dp[0][0] = 1
    for i in range(n):
        ai = a[i]
        for j in range(i+1)[::-1]:
            nj = j+1
            for k in range(s)[::-1]:
                if dp[k][j] == 0:
                    continue
                nk = k+ai
                if nk > s:
                    continue
                dp[nk][nj] += dp[k][j]
    ans = 0
    for i in range(n+1):
        if dp[s][i]:
            ans += dp[s][i]*pow(2,n-i,mod)%mod
            ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 998244353

def solve():
    n,s = LI()
    a = LI()
    dp = [0]*(s+1)
    dp[0] = pow(2,n,mod)
    inv = pow(2,mod-2,mod)
    for i in a:
        for k in range(s)[::-1]:
            nk = k+i
            if nk > s:
                continue
            dp[nk] += dp[k]*inv%mod
            dp[nk] %= mod
    print(dp[s])
    return

#Solve
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

import re
n=int(input())
s=input()
ans=0
for i in range(10):
    for j in range(10):
        for k in range(10):
            p=r'.*'+str(i)+r'.*'+str(j)+r'.*'+str(k)+r'.*'
            x=re.search(p, s)
            if x:
                ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
ans=0
for i in range(10):
    for j in range(10):
        for k in range(10):
            x=s.find(str(i))
            y=s.find(str(j),x+1)
            z=s.find(str(k),y+1)
            if(x!=-1 and y!=-1 and z!=-1):
                ans+=1
print(ans)
### BUGGY CODE ###

# coding: utf-8
n = int(input())
A = list(map(int, input().split()))
ans = 1
for i in range(n):
    ans *= A[i]
if(ans > 1000000000000000000):
    print("-1")
else:
    print(ans)

### FIXED CODE ###

# coding: utf-8
n = int(input())
A = list(map(int, input().split()))
ans = 1
for i in range(n):
    ans *= A[i]
    if(ans > 1000000000000000000):
        if 0 in A:
            print("0")
            quit()
        else:
            print("-1")
            quit()
print(ans)
### BUGGY CODE ###

from itertools import accumulate
from collections import Counter


n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
    a_acc = Counter(accumulate(a[i:]))
    if 0 in a_acc.keys():
        ans += a_acc[0]
print(ans)

### FIXED CODE ###

from collections import Counter


n = int(input())
a = list(map(int, input().split()))
b = 0
c = Counter([0])
ans = 0
for i in range(n):
    b += a[i]
    ans += c[b]
    c[b] += 1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import defaultdict
import sys
input = sys.stdin.buffer.readline
LI = lambda:map(int, input().split())
II = lambda:int(input())

#solve
def solve():
    n = II()
    vw = []
    nbit = 1 << n.bit_length()
    M = 10 ** 5 + 1
    M0 = [0] * M
    d = [M0]
    dp = [[]]
    XX = 1 << n.bit_length() // 2
    for i in range(1, n + 1):
        v, w = LI()
        vw.append((v, w))
        if i < XX:
            di = d[i // 2][:]
            for j in range(M - 1, w - 1, -1):
                if di[j] < di[j - w] + v:
                    di[j] = di[j - w] + v
            d.append(di)

    for _ in range(II()):
        V, L = LI()
        lent = V.bit_length()
        n1 = lent // 2
        n2 = lent - n1
        vw2 = []
        for _ in range(n2):
            vw2.append((vw[V - 1][0], vw[V - 1][1]))
            V //= 2
        lw = [0] * (1 << n2)
        lv = [0] * (1 << n2)
        dv = d[V]
        ans = dv[L]
        for mask in range(1, 1 << n2):
            a = mask & -mask
            b = a.bit_length() - 1
            v, w = vw2[b]
            ww = lw[mask - a] + w
            lw[mask] = ww
            if ww > L: continue
            vv = lv[mask - a] + v
            lv[mask] = vv
            if dv[L - ww] + vv > ans:
                ans = dv[L - ww] + vv
        print(ans)
    return


solve()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

#solve
def solve():

    input = sys.stdin.buffer.readline
    LI = lambda: map(int, input().split())
    II = lambda: int(input())
    n = II()
    vw = [[]] * n
    M = 10 ** 5 + 1
    M0 = [0] * M
    XX = 1 << 10
    d = [[]] * XX
    d[0] = M0

    for i in range(1, min(XX, n + 1)):
        v, w = LI()
        vw[i - 1] = (v, w)
        di = d[i // 2][:]
        for j in range(M - 1, w - 1, -1):
            if di[j] < di[j - w] + v:
                di[j] = di[j - w] + v
        d[i] = di

    for i in range(XX, n + 1):
        v, w = LI()
        vw[i - 1] = (v, w)

    Vv = [i.bit_length() for i in range(1 << 18)]
    n = [pow(2, i) for i in range(18)]
    lentl = [i - 10 for i in range(19)]
    maskset = [[]] * n[10]

    for i in range(1, 11):
        for mask in range(n[i - 1], n[i]):
            a = mask & -mask
            b = Vv[a] - 1
            maska = mask - a
            maskset[mask - 1] = (mask, b, maska)

    for _ in range(II()):
        V, L = LI()

        if V < XX:
            print(d[V][L])
            continue

        n2 = lentl[Vv[V]]
        vw2 = [None] * n2

        for i in range(n2):
            vw2[i] = (vw[V - 1][0], vw[V - 1][1])
            V //= 2

        lw = [0] * n[n2]
        lv = [0] * n[n2]
        dv = d[V]
        ans = dv[L]

        for i in range(n[n2] - 1):
            mask, b, maska = maskset[i]
            v, w = vw2[b]
            ww = lw[maska] + w
            Lww = L - ww
            lw[mask] = ww
            if Lww < 0: continue
            vv = lv[maska] + v
            lv[mask] = vv
            tmp = dv[Lww] + vv
            if tmp > ans:
                ans = tmp
        print(ans)
    return

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

n = int(input())
ans = 1
for i in range(1, n + 1):
    ans *= i

print(ans % (10 ** 9 + 7))


### FIXED CODE ###

n = int(input())
ans = 1
for i in range(1, n + 1):
    ans *= i
    ans %= (10 ** 9 + 7)

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

N = int(input())

total = 0
for i in range(1, N + 1):
    N_max = N // i * i
    num = N // i
    total += (N_max + i) * (num // 2)
    if num%2:
        total += (N_max + i) // 2
print(total)

### FIXED CODE ###

N = int(input())

total = 0
for i in range(1, N + 1):
    a = N // i
    total += (a * i + i) * a
    # if num%2:
    #     total += (N_max + i) // 2
print(int(total / 2))
### BUGGY CODE ###

from itertools import combinations

n = int(input())
s = input()

print(len(set([a+b+c for a,b,c in combinations(s, 3)])))

### FIXED CODE ###

from collections import defaultdict
import bisect
from itertools import product

n = int(input())
s = input()

# {文字:その文字の出現位置}の辞書を構築
d = defaultdict(list)
for i in range(n):
    d[s[i]].append(i)

def canCreate(x,y,z):
    pos = 0
    for c in map(str, [x,y,z]):
        pos = bisect.bisect_left(d[c], pos)
        if pos == len(d[c]):
            return False
        pos = d[c][pos] + 1
    return True

ans = sum([canCreate(x, y, z) for x,y,z in product(range(10), repeat=3)])

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

#!/usr/bin/env python3
import sys

def solve(N: int, T: int, A: "List[int]", B: "List[int]"):
    dp = [0] * (T + 1)
    for a, b in sorted(zip(A, B), reverse=True):
        for t in range(T):
            dp[t] = max(dp[t],
                        b + (dp[t+a] if t + a < T else 0))
    return max(dp)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    print(solve(N, T, A, B))

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int, T: int, A: "List[int]", B: "List[int]"):
    dp = [0] * (T + 1)
    for a, b in sorted(zip(A, B), reverse=True):
        for t in range(T):
            dp[t] = max(dp[t],
                        b + (dp[t+a] if t + a < T else 0))
    return max(dp)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    print(solve(N, T, A, B))

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

import sys
input = sys.stdin.readline

N, P = map(int, input().split())
S = list(map(int, list(input().rstrip())))
ans = 0
if P == 2 or P == 5:
    for i in range(N):
        if S[i] % P == 0:
            ans += i + 1
else:
    U = [0] * (N+1)
    count = [0] * P
    count[0] = 1
    for i in range(N)[::-1]:
        x = S[i] * 10**(N-i-1) + U[i+1]
        U[i] = (S[i] * 10**(N-i-1) + U[i+1]) % P
        ans += count[U[i]]
        count[U[i]] += 1
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N, P = map(int, input().split())
S = list(map(int, list(input().rstrip())))
ans = 0
if P == 2 or P == 5:
    for i in range(N):
        if S[i] % P == 0:
            ans += i + 1
else:
    U = [0] * (N+1)
    count = [0] * P
    count[0] = 1
    factor = 10
    for i in range(N)[::-1]:
        U[i] = (S[i] * factor + U[i+1]) % P
        factor = factor * 10 % P
        ans += count[U[i]]
        count[U[i]] += 1
print(ans)
### BUGGY CODE ###

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

n = int(input())
s = [input() for i in range(n)]
cnt = 0
for i in range(0, n-1):
    stype1 = {}
    for j in range(10):
        if s[i][j] in stype1:
            stype1[s[i][j]] += 1
        else:
            stype1[s[i][j]] = 1
    for k in range(i+1, n):
        stype2 = {}
        for l in range(10):
            if s[k][l] in stype2:
                stype2[s[k][l]] += 1
            else:
                stype2[s[k][l]] = 1
        if stype1 == stype2:
            cnt += 1
print(cnt)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
d = {}
ans = 0
n = int(input())
s = [''.join(sorted(input())) for i in range(n)]
for string in s:
    if string in d:
        ans += d[string]
        d[string] += 1
    else:
        d[string] = 1
print(ans)
### BUGGY CODE ###

otoshidama = list(map(int,input().split()))
flg = True
while flg:
    for i in range(otoshidama[0]+1):
        yukichi =i
        for n in range(otoshidama[0]-yukichi+1):
            higuchi =n
            noguchi = otoshidama[0]-yukichi - higuchi

            if 10000*yukichi+5000*higuchi+1000*noguchi==otoshidama[1]:
                print("{} {} {}".format(yukichi,higuchi,noguchi))
                flg = False
                break
        if flg == False:
            break

if flg:
    print("-1 -1 -1")

### FIXED CODE ###

otoshidama = list(map(int,input().split()))
flg = True
for i in range(otoshidama[0]+1):
    yukichi =i
    for n in range(otoshidama[0]-yukichi+1):
        higuchi =n
        noguchi = otoshidama[0]-yukichi - higuchi

        if 10000*yukichi+5000*higuchi+1000*noguchi==otoshidama[1]:
            print("{} {} {}".format(yukichi,higuchi,noguchi))
            flg = False
            break
    if flg == False:
        break

if flg:
    print("-1 -1 -1")