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

n,a = map(int,input().split())
x = list(map(int,input().split()))
ans = 0
def dfs(sum, cnt, num):
    global ans
    if cnt==n:
        if num!=0 and sum/num==a:
            ans = ans + 1
        return 1
    dfs(sum+x[cnt],cnt+1,num+1)
    dfs(sum,cnt+1,num)
    return 1
dfs(0,0,0)
print(ans)

### FIXED CODE ###

n,a = map(int,input().split())
x = list(map(int,input().split()))
mx = max(x)
mx = max(mx,a)
dp = [[[0]*(n*mx+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(1,n+1):
    for j in range(i+1):
        for k in range(n*mx+1):
            if k<x[i-1]:
                dp[i][j][k] = dp[i-1][j][k]
            elif j>0 and k>=x[i-1]:
                dp[i][j][k] = dp[i-1][j][k]+dp[i-1][j-1][k-x[i-1]]
ans = 0
for i in range(n+1):
        ans += dp[n][i][a*i]
print(ans-1)
### BUGGY CODE ###

n= int(input())
a = list(int(i) for i in input().split())
a2 = list(set(a))
ans = 0
for i in a2:
  tmp = a.count(i)
  if tmp <i:
   ans += tmp
  else:
   ans += (tmp-i)
print(ans)

### FIXED CODE ###

import collections
n= int(input())
a = list(int(i) for i in input().split())
c = collections.Counter(a)
a2 = list(set(a))
ans = 0
for i in a2:
  tmp = c[i]
  if tmp <i:
   ans += tmp
  else:
   ans += (tmp-i)
print(ans)
### BUGGY CODE ###

from numpy import gcd 
K = int(input())+1
cnt = 0
for a in range(1,K):    
    for b in range(1,K):
        for c in range(1,K):
            cnt+=gcd((gcd(b,c)),a)        
print(cnt)
        

### FIXED CODE ###

from math import gcd
k = int(input())+1
ans = 0
for i in range(1,k):
    for j in range(1,k):
        for l in range(1,k):
            ans+=gcd(gcd(i,j),l)
print(ans)
### BUGGY CODE ###

N = int(input())
M = list(map(int, input().split()))
M = sorted(M)
count = 0
for i in range(N):
  a = M[i]
  for j in range(i+1, N):
    b = M[j]
    upper = a+b
    l, r = j, N
    while (r - l) > 1:
      c = (l + r) // 2
      if M[c] < upper:
        l = c
      else:
        r = c  
    #print(count, j, l, r)
    count += l - j
      
print(count)

### FIXED CODE ###

N = int(input())
M = list(map(int, input().split()))
M = sorted(M)
count = 0
for i in range(N):
  a = M[i]
  for j in range(i+1, N):
    b = M[j]
    upper = a+b
    l, r = j, N
    while (r - l) > 1:
      c = (l + r) // 2
      if M[c] < upper:
        l = c
      else:
        r = c  
    #print(count, j, l, r)
    count += l - j
      
print(count)
### BUGGY CODE ###

import math

K=int(input())
sum=0

for i in range(K):
  for j in range(K):
    for k in range(K):
       sum+=math.gcd(math.gcd(i+1,j+1),k+1)    
print(sum)

### FIXED CODE ###

from math import gcd

K=int(input())+1
sum=0

for i in range(1,K):
  for j in range(1,K):
    for k in range(1,K):
       sum+=gcd(gcd(i,j),k)    
print(sum)
### BUGGY CODE ###

N,K = map(int,input().split(' '))
S = input()
previous_idx = 0
if S[0] == 'L':
    search_s = 'R'
    non_search_s = 'L'
else:
    search_s = 'L'
    non_search_s = 'R'

continue_flag = False
idx = 0
lst_idx =  -5
new_S = ''
while K != 0 and idx != N:
    if S[idx] == search_s:
        if not continue_flag:
            continue_flag = True
        new_S += non_search_s
    else:
        if continue_flag:
            continue_flag = False
            K -= 1
            last_idx = idx
        new_S += S[idx]
    idx += 1
new_S += S[idx:N]
#print(new_S)

count_s = 0
previous_s = new_S[0]
for i in range(1,N):
    if previous_s == new_S[i]:
        count_s +=1
    else:
        previous_s = new_S[i]
print(count_s)


### FIXED CODE ###

N,K = map(int,input().split(' '))
S = input()
previous_idx = 0
if S[0] == 'L':
    search_s = 'R'
    non_search_s = 'L'
else:
    search_s = 'L'
    non_search_s = 'R'

flag  = False
i = 0
count_s = 0
new_S = ''
previous_s = S[0]
while K != 0 and i != N:
    if previous_s != S[i]:
        if previous_s == search_s:
            #new_S += non_search_s*count_s
            K -= 1
        #else:
            #new_S += non_search_s*count_s
        previous_s = S[i]
        #count_s = 1
        #count_s += 1
        #if i+1 == N:
        #    flag =True
            #new_S += non_search_s*count_s
        
    i += 1
if K > 0:
    print(N-1)
else:
    new_S += non_search_s*(i-1)
    if not flag:
        new_S += S[i-1:N]
    #print(new_S)
    count_s = 0
    previous_s = new_S[0]
    for i in range(1,N):
        if previous_s == new_S[i]:
            count_s +=1
        else:
            previous_s = new_S[i]
    print(count_s)
### BUGGY CODE ###

# inverse x^(-1)
def inv(x):
    global mod
    return pow(x,mod-2,mod)

mod=10**9+7
N = int(input())
C = [0]
C.extend(sorted(list(map(int,input().split())), reverse=True)) # 1-indexed, 降順

# print(C)
# C[i]が最後からj番目に操作される（コストが C[i]*j 掛かる）のは，c[1]~C[i-1]にj-1個操作すべきもの，すなわち，C[i]以上のものがあるとき。
# C[i+1]~C[N]の選び方は自由。
# ⇒ combi(i-1, j-1)*2**(N-i) を掛ける。

fact = [1]; invfact = [1]; pow2 = [1]
for k in range(1, N+1):
    fact.append(fact[-1] * k % mod)
    invfact.append(inv(fact[-1]))
    pow2.append(pow2[-1] * 2 % mod)

# print(fact)
# print(invfact)
# print(pow2)

ans=0
for i in range(1, N+1):
    for j in range(1, i+1):
        c = fact[i - 1] * invfact[j - 1] * invfact[i - j] * pow2[N - i] % mod
        # print(i, j, c)
        ans += C[i] * j * c
    ans = ans % mod

ans = ans * pow(2, N, mod) % mod

print(ans)

### FIXED CODE ###

# inverse x^(-1)
def inv(x):
    global mod
    return pow(x,mod-2,mod)

mod=10**9+7
N = int(input())
C = [0]
C.extend(sorted(list(map(int,input().split())), reverse=True)) # 1-indexed, 降順

# print(C)
# C[i]が最後からj番目に操作される（コストが C[i]*j 掛かる）のは，c[1]~C[i-1]にj-1個操作すべきもの，すなわち，C[i]以上のものがあるとき。
# C[i+1]~C[N]の選び方は自由。
# ⇒ combi(i-1, j-1)*2**(N-i) を掛ける。
# 総和を計算すると，結局，2**N * Σ[i=1->N](2**(N-i)*Ci*(2**(i-2)*(i-1) + 2**(i-1))) になる

pow2 = [1]
for k in range(1, N+1):    
    pow2.append(pow2[-1] * 2 % mod)

# print(pow2)

ans=0
for i in range(1, N+1):
    temp = pow2[N - i] * C[i] * ((0 if i == 1 else (pow2[i - 2] * (i - 1))) + pow2[i - 1]) % mod
    ans = (ans + temp) % mod

ans = ans * pow2[N] % mod

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

n,m = map(int,input().split())
li = list(map(int,input().split()))
tmp_li = []
for _ in range(m):
    b,c = map(int,input().split())
    tmp_li.append([c,b])
tmp_li.sort(reverse=True)
#print(tmp_li)
count = 0
for t in tmp_li:
    li += [t[0]]*t[1]
    if count + t[1]>=n:
        break
li.sort(reverse=True)
print(sum(li[:n]))

### FIXED CODE ###

n,m = map(int,input().split())
li = list(map(int,input().split()))
tmp_li = []
for _ in range(m):
    b,c = map(int,input().split())
    tmp_li.append((c,b))
tmp_li.sort(reverse=True)
#print(tmp_li)
for c,b in tmp_li:
    li.extend([c]*b)
    if len(li)>= 2*n:
        break
li.sort(reverse=True)
print(sum(li[:n]))
### BUGGY CODE ###

N=int(input())
paper=[]
for i in range(N):
  a=int(input())
  try:
    del paper[paper.index(a)]
  except:
    paper.append(a)
print(len(paper))

### FIXED CODE ###

N=int(input())
paper={}
for i in range(N):
  a=input()
  if a in paper:
    paper[a]+=1
  else:
    paper[a]=1
counter=0
for key in paper.keys():
  if int(paper[key])%2==1:
    counter+=1
print(counter)
### BUGGY CODE ###

N,W=map(int,input().split())
w,v=[None]*N,[None]*N
inf=float('inf')
dp=[[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(N):
  w[i],v[i]=map(int,input().split())

for i in range(N-1,-1,-1):
  for j in range(W+1):
    if j<w[i]:
      dp[i][j]=dp[i+1][j]
    else:
      dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])

print(dp[0][W])

### FIXED CODE ###

from collections import defaultdict as dd
from itertools import accumulate as ac
from itertools import product as pr

N,W=map(int,input().split())
d=dd(list)
for _ in range(N):
  w,v=map(int,input().split())
  d[w].extend([v])
d=dict(d)
for i in d.keys():
  d[i].sort(reverse=True)
  d[i]=[0]+list(ac(d[i]))

l=[]
key=list(d.keys())
for val in pr(*map(enumerate,d.values())):
  weight=sum(map(lambda x,y:x*y[0],key,val))
  value=sum(map(lambda x:x[1],val))
  if weight<=W:
    l.extend([value])

print(max(l))
### BUGGY CODE ###

import itertools

N = int(input())
S = input()
s = list(S)

a = list(itertools.combinations(s, 3))
A = []

for i in range(len(a)):
  if a[i] not in A:
    A.append(a[i])
else:
  print(len(A))

### FIXED CODE ###

N = int(input())
S = input()
s = list(S)

count = 0

for i in range(1000):
  ss = s[:]
  st = str(i).rjust(3, '0')
  if st[0] in ss:
    del ss[0:(ss.index(st[0])+1)]
    if st[1] in ss:
      del ss[0:(ss.index(st[1])+1)]
      if st[2] in ss:
        count += 1
else:
  print(count)
### BUGGY CODE ###

import bisect
n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

A.sort()
B.sort()
C.sort()
ans=0
for a in A:
  bidx=bisect.bisect_right(B,a)
  if bidx==len(B): break
  for b in B[bidx:]:
    cidx=bisect.bisect_right(C,b)
    if cidx==len(B): break
    ans+=len(C)-cidx
print(ans)


### FIXED CODE ###

import bisect
n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

A.sort()
B.sort()
C.sort()
ans=0
for b in B:
  aidx=bisect.bisect_left(A,b)
  cidx=bisect.bisect_right(C,b)
  ans+=aidx*(len(C)-cidx)
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
M = {}
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            M[S[i]+S[j]+S[k]] = 1
print(len(M))

### FIXED CODE ###

import string
N = int(input())
S = input()
L = []
for i in string.digits:
    for j in string.digits:
        for k in string.digits:
            L.append((i,j,k))
count = 0
for l in L:
    if l[0] not in S:
        continue
    S2 = S[S.index(l[0])+1:]
    if l[1] not in S2:
        continue
    S3 = S2[S2.index(l[1])+1:]
    if l[2] not in S3:
        continue
    count += 1
print(count)
### BUGGY CODE ###

import bisect
n = int(input())
alis = sorted(list(map(int, input().split())))
blis = sorted(list(map(int, input().split())))
clis = sorted(list(map(int, input().split())))
bc = [0]*n
for i in range(n):
    bc[i] = n - bisect.bisect_right(clis, blis[i])
ans = 0
for i in range(n):
    index = bisect.bisect_right(blis, alis[i])
    ans += sum(bc[index:])
print(ans)

### FIXED CODE ###

from bisect import bisect_left, bisect_right, bisect
n = int(input())
alis = sorted(list(map(int, input().split())))
blis = list(map(int, input().split()))
clis = sorted(list(map(int, input().split())))
ans = 0
for b in blis:
    up = bisect_left(alis, b)
    down = n - bisect(clis, b)
    ans += up*down
print(ans)
### BUGGY CODE ###

import itertools

if __name__ == '__main__':

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

	total = 0
	C = list(itertools.combinations(A, 2))
	B = [v[0]*v[1] for v in C]
	print(sum(B)%(10**9+7))


### FIXED CODE ###

if __name__ == '__main__':

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

    #全体
    sm = sum(A) ** 2
    #共通部分
    com = sum([i * i for i in A])

    ans = (sm - com) // 2
    print(ans%(10**9+7))
### BUGGY CODE ###

N,K=map(int,input().split())
L=list(map(int,input().split()))
M=0
M_IND=0
for i in range(len(L)-(K-1)):
  tmp = L[i]
  for j in range(i+1, i+K):
    tmp += L[j]
  #print(tmp)
  if M < tmp:
    M = tmp
    M_IND=i
#print(M_IND)
#for k in range(L[M_IND,M_IND+K])
ANS=0
for i in L[M_IND:M_IND+K]:
  #print(i)
  ex = 0
  p = 1/i
  for x in range(i+1):
      px = p*x
      ex += px
  ANS += ex
print(ANS)

### FIXED CODE ###

def kitai(n):
  return (int(n)+1)/2

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

L=np.array([list(map(kitai, input().split()))]).reshape(-1)

from itertools import accumulate

acc = [0]+ list(accumulate(L)) # 0を忘れずに
ans = 0
for i in range(n-k+1):
  ans = max(ans,acc[i+k]-acc[i])
print(ans)
### BUGGY CODE ###

def cns(ls,m,sm):
    global n, s
    count = 0
    if m == n:
        if sm == s:
            return 1
        else:
            return 0
    elif sm <= s:
        for i in range(9-m+1):
            rls = ls[:]
            k = rls.pop(i)
            count += cns(rls,m+1,sm+(m+1)*k)
        return count
    else:
        return 0

ls = [0,1,2,3,4,5,6,7,8,9]
while True:
    n, s = map(int, raw_input().split())
    print cns(ls,0,0)

### FIXED CODE ###

def mxmn(ls,m):
	global n
	s1,s2 = 0, 0
	for i in range(m):
		s1 += (n-i)*ls[-i-1]
		s2 += (n-i)*ls[i]
	return s1,s2

def f(ls,m,s):
	global n
	count = 0
	if m > 0:
		mx,mn = mxmn(ls,m)
		if mx < s or mn > s: return 0
		elif mx == s or mn == s: return 1
		for i in range(len(ls)):
			lls = ls[:]
			a = (n-m+1)*lls.pop(i)
			if s-a < 0:	break
			else: count += f(lls,m-1,s-a)
		return count
	else:
		return 1 if s == 0 else 0
			
ls = [i for i in range(10)]
while True:
	try:
		n,s = map(int, raw_input().split())
		print f(ls,n,s)
	except:
		break
### BUGGY CODE ###

def main():
    N = int(input())
    A_list = list(map(int, input().split()))
    mod = 10**9 + 7

    ans = 0
    for i in range(N):
        A = A_list[i]
        A_ = A_list[i+1:]
        ans = (ans + (A * sum(A_) % mod)) % mod
    print(ans)
    return



if __name__ == '__main__':
    main()
    

### FIXED CODE ###

def main():
    N = int(input())
    A_list = list(map(int, input().split()))
    mod = 10**9 + 7

    ans = 0
    A_ = sum(A_list) % mod
    for i in range(N-1):
        A = A_list[i]
        A_ = A_ - A
        ans = (ans + (A * A_) % mod) % mod
    print(ans)
    return


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

import sys

input = sys.stdin.readline

def main():
    n = int(input().rstrip())
    a = list(map(int, input().rstrip().split()))
    count = 0
    b = []
    for i in range(n):
      count_temp = 0
      if not a[i] in b:
        for k in range(n):
          if i != k and a[i] % a[k] == 0:
            count_temp += 1
            break
        if count_temp == 0:
          count += 1
          b.append(a[i])
    print(count)
  
if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import Counter
import sys
n=int(input())
a=sorted(list(map(int,input().split())))
 
c=[1 for i in range(10**6+1)]
d = Counter(a)
s = list(set(a))
count = 0
if d[1] == 1:
  print(1)
  sys.exit()
elif d[1] >=2:
  print(0)
  sys.exit()
for x in s:
  t = x * 2
  while t <= 10 ** 6:
    c[t] = 0
    t += x
 
for x in a:
  if d[x] == 1 and c[x] == 1:
    count += 1
print(count)
### BUGGY CODE ###

import re

N = int(input())
S = input()

rex = r'([^_])\1{0,}'
pattern = re.compile(rex)

matchobj = pattern.search(S)
while matchobj:
    S = pattern.sub("_", S, 1)
    matchobj = pattern.search(S)
print(len(S))


### FIXED CODE ###

import re

N = int(input())
S = input()

rex = r'(.)\1{0,}'
pattern = re.compile(rex)
ans = pattern.findall(S)

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

import sys
input=sys.stdin.readline

n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
#print(l)
li=sorted(l)
#print(li)
for i in l:
    a=li.index(i)+1
    if i[0]>=2:
        for j in l:
            if i[0]>j[0]:
                a-=1
    print(str('%06d'%i[0])+str('%06d'%a)) 

### FIXED CODE ###

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
s=[]
for i in enumerate(l):
    s.append(i)
s=sorted(s,key=lambda x:(x[1][0],x[1][1]))
#print(s)
a=1
for i in range(m):
    if i==0:
        s[0][1][1]=1
    elif s[i][1][0]==s[i-1][1][0]:
        a+=1
        s[i][1][1]=a
    elif s[i][1][0]!=s[i-1][1][0]:
        a=1
        s[i][1][1]=a
#print(s)
s=sorted(s,key=lambda x:x[0])
#print(s)
for i in s:
    print('%06d'%i[1][0]+'%06d'%i[1][1])
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
used = [[False] * (w+2) for _ in range(h+2)]
for r in range(h+2):
    used[r][0] = True
    used[r][-1] = True
for c in range(w+2):
    used[0][c] = True
    used[-1][c] = True
que = deque([])
for r in range(h):
    line = input()
    for c in range(w):
        if line[c] == "#":
            que.append((r+1, c+1, 0))
            used[r+1][c+1] = 0
neighbors = [(1,0), (0,1), (-1,0), (0,-1)]
while que:
    r, c, k = que.popleft()
    for dr, dc in neighbors:
        nr, nc = r+dr, c+dc
        if not used[nr][nc]:
            que.append((nr, nc, k+1))
            used[nr][nc] = True
print(k)

### FIXED CODE ###

from collections import deque

def solve(h, w, a):
    used = [[True] * (w+2) for _ in range(h+2)]
    que = deque()
    for r in range(h):
        used[r+1][1:-1] = map(lambda _:_=="#", a[r])
        for c in range(w):
            if a[r][c] == "#":
                que.append((r+1, c+1, 0))
    neighbors = [(1,0), (0,1), (-1,0), (0,-1)]
    while que:
        r, c, k = que.popleft()
        for dr, dc in neighbors:
            nr, nc = r+dr, c+dc
            if not used[nr][nc]:
                que.append((nr, nc, k+1))
                used[nr][nc] = True
    return k

h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(solve(h, w, a))
### BUGGY CODE ###

s = input()
abc_index = s.find("ABC")
ans = 0
while abc_index >= 0:
    s = s.replace("ABC","BCA",1)
    ans += 1
    abc_index = s.find("ABC")
print(ans)

### FIXED CODE ###

s = input()
s = s.replace('BC','D')
A_count = 0
ans = 0

for i in s:
    if i == 'A':
        A_count += 1
    elif i == 'B' or i == 'C':
        A_count = 0
    else:
        ans += A_count
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from heapq import heappop, heappush
def inpl(): return map(int, input().split())
N = int(input())

X = []
Y = []

for i in range(N):
    x, y = inpl()
    X.append((i, x))
    Y.append((i, y))

X = sorted(X, key=lambda x: x[1])
Y = sorted(Y, key=lambda y: y[1])

G = [[] for _ in range(N)]
for i in range(N-1):
    Xa, Xb = X[i], X[i+1]
    Ya, Yb = Y[i], Y[i+1]
    G[Xa[0]].append([Xb[0], Xb[1]-Xa[1]])
    G[Xb[0]].append([Xa[0], Xb[1]-Xa[1]])
    
    G[Ya[0]].append([Yb[0], Yb[1]-Ya[1]])
    G[Yb[0]].append([Ya[0], Yb[1]-Ya[1]])

visited = [False]*N
Q = [(0, 0)]
ans = 0

while Q:
    c, n = heappop(Q)
    if visited[n]:
        continue
    visited[n] = True
    ans += c
    
    for m, d in G[n]:
        if visited[m]:
            continue
        else:
            heappush(Q, (d, m))

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))

n = int(input())
X = []
Y = []
for i in range(n):
    x, y = inpl()
    X.append((x, i))
    Y.append((y, i))

X = sorted(X, key = lambda x: x[0])
Y = sorted(Y, key = lambda y: y[0])

G = [[] for _ in range(n)]
edges = []
for i in range(n-1):
    edges.append((X[i][1], X[i+1][1], abs(X[i][0] - X[i+1][0])))
    edges.append((Y[i][1], Y[i+1][1], abs(Y[i][0] - Y[i+1][0])))

edges = sorted(edges, key = lambda e: e[2])

tree = [[-1, 1] for _ in range(n)]

def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0])    
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px

res = 0

for s, t, w in edges:
    if find(s) != find(t):
        unite(s, t)
        res += w
print(res)
### BUGGY CODE ###

s=input()
p=0
c=0
while p<len(s)-1:
    if (s[p]=='0' and s[p+1]=='1') or (s[p]=='1' and s[p+1]=='0'):
        s=s[:p]+s[p+2:]
        
        c+=2
        p=0
    else:
        p+=1
print(c)


### FIXED CODE ###

s=input()
a=s.count('0')
b=s.count('1')
if a>=b:
    print(b*2)
else:
    print(a*2)
### BUGGY CODE ###

def isPrime(n):
    if n <= 2:
        return n == 2
    if (n % 2 == 0):
        return False
    for i in range(2, n // 2 + 1):
        if n % i == 0:
            return False
    return True


N = int(input())
print(len(list(filter(isPrime, [int(input()) for i in range(N)]))))



### FIXED CODE ###

import math

def isPrime(n):
    if n <= 2:
        return n == 2
    if (n % 2 == 0):
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

N = int(input())
print(len(list(filter(isPrime, [int(input()) for i in range(N)]))))
### BUGGY CODE ###

import math
A, B, N = map(int, input().split())
ans = 0


for x in range(1, N+1):
    tmpans = math.floor((A * x)/B) - (A * math.floor(x/B))
    ans = max(tmpans, ans)
print(ans)


### FIXED CODE ###

import math

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

if N < B:
    x = N
else:
    x = B - 1

def check(x):
    return math.floor((A * x) / B)
            
print(check(x))
### BUGGY CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

N, Q = map(int, input().split())
repn = [[] for i in range(N)]

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

count = [0] * N

## analysis of tree structure
parent = [-1] + ['nul'] * (N - 1)
child = [[] for i in range(N)]
child[0] = repn[0]

for v in child[0]:
    parent[v] = 0

deq = deque(repn[0])

while deq:
    v = deq.popleft()
    for w in repn[v]:
        if parent[v] == w:
            pass
        else:
            parent[w] = v
            child[v].append(w)
            deq.append(w)

multi_child = [[] for i in range(N)]


# make a function
def add(lst, p, x):
    if child[p] == []:
        lst[p] += x
    else:
        lst[p] += x
        for v in child[p]:
            add(lst, v, x)

## soltion
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    add(count, p, x)
    
print(' '.join(map(str, count)))

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

N, Q = map(int, input().split())
repn = [[] for i in range(N)]

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

count = [0] * N

## analysis of tree structure
parent = [-1] + ['nul'] * (N - 1)
child = [[] for i in range(N)]
child[0] = repn[0]

for v in child[0]:
    parent[v] = 0

deq = deque(repn[0])

while deq:
    v = deq.popleft()
    for w in repn[v]:
        if parent[v] == w:
            pass
        else:
            parent[w] = v
            child[v].append(w)
            deq.append(w)


## soltion
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    count[p] += x
    
deq = deque([0])
while deq:
    v = deq.popleft()
    for w in child[v]:
        count[w] += count[v]
        deq.append(w)



print(' '.join(map(str, count)))
### BUGGY CODE ###

import math
 
def gcd(x, y):
	while y != 0:
		z = x % y
		x = y
		y = z
	return x
 
a, b = map(int, input().split())
x    = gcd(a, b)
y    = x // 2 + 1
ds   = [1]

if x % 2 == 0:
	ds.append(2)

for i in range(3, y + 1, 2):
	if x % i == 0:
		ds.append(i)

if 2 < x:
	ds.append(x)

fs = [True] * len(ds)

for i in range(1, len(fs)):
	if fs[i] == False:
		continue;
	for j in range(i + 1, len(fs)):
		if ds[j] % ds[i] == 0:
			fs[j] = False

print(sum(1 for f in fs if f == True))


### FIXED CODE ###

import math
 
def gcd(x, y):
	while y != 0:
		z = x % y
		x = y
		y = z
	return x
 
a, b = map(int, input().split())
x    = gcd(a, b)
y    = int(math.sqrt(x))
c    = 1

for i in range(2, y + 1):
	if y < i:
		break;
	if x % i == 0:
		c += 1
		while x % i == 0:
			x //= i
			
if 1 < x:
	c += 1

print(c)
### BUGGY CODE ###

def solve():
    s = input()

    ans = 0
    if len(s) >= 5:
        for i in range(5, len(s)):
            for j in range(i):
                for k in range((len(s)-j)//i):
                    if int(s[i*k+j:i*(k+1)+j]) % 2019 == 0:
                        ans += 1
                        #print(i*k+j, i*(k+1)+j)
                        #print(s[i*k+j:i*(k+1)+j])
    print(ans)
    
solve()

### FIXED CODE ###

S=input()
N=len(S)
M=2019

remainder=[0]*M
val=0
for i in range(N):
  val=(int(S[N-1-i])*pow(10,i,M)+val)%M
  remainder[val]+=1

ans=remainder[0]
for i in range(2019):
  ans+=remainder[i]*(remainder[i]-1)//2
print(ans)
### BUGGY CODE ###

a, b = map(int, input().split())
for i in range (a,b):
  a *= i
if a < 0 :
  print("Negative")
elif a==0:
  print("Zero")
elif a> 0:
  print("Positive")
  

### FIXED CODE ###

a,b = map(int, input().split())
if a> 0:
  print("Positive")
elif b< 0 :
  if (b-a) % 2 == 0:
    print("Negative")
  else :
    print("Positive")
else : 
  print("Zero")