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

import numpy as np
def seachPrimeNum(N):
  max = int(np.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

n=10**5
a=seachPrimeNum(n)
b=[]
y=0
x=0
while x<=100000:
  t=a[y]
  x=t*2-1
  b.append(x)
  y+=1
  
c=set(a)&set(b)

q=int(input())
for p in range(q):
  ans=0
  w,z=map(int,input().split())
  for j in c:
    if w<=j<=z:
      ans+=1
    if j<w or z<j:
      continue
  print(ans)



### FIXED CODE ###

import numpy as np
def seachPrimeNum(N):
  max = int(np.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

n=10**5
a=seachPrimeNum(n)
b=[]
y=0
x=0
while x<=100000:
  t=a[y]
  x=t*2-1
  b.append(x)
  y+=1
  
c=set(a)&set(b)

q=int(input())
r=[0 for _ in range(100000)]
for f in c:
  r[f]=1
for g in range(len(r)-1):
  r[g+1]=r[g]+r[g+1]

for p in range(q):
  w,z=map(int,input().split())
  print(r[z]-r[w-1])
### BUGGY CODE ###

import numpy as np
MOD = 10**9 + 7
H, W = map(int, input().split())
field = [['#'] * (W + 2)]
for i in range(H):
    field.append(list('#' + input() + '#'))
field.append(['#'] * (W + 2))

dp = np.zeros((H+2, W+2),dtype=int)
dp[H][W] = 1

for i in range(H,0,-1):
    for j in range(W,0,-1):
        if field[i][j] == '#':
            continue
        if field[i-1][j] == '.':
            dp[i-1][j] += dp[i][j]
            dp[i-1][j] %= MOD
        if field[i][j-1] == '.':
            dp[i][j-1] += dp[i][j]
            dp[i][j-1] %= MOD
print(dp[1][1])

### FIXED CODE ###

MOD = 10**9 + 7
H, W = map(int, input().split())
field = [['#'] * (W + 2)]
for i in range(H):
    field.append(list('#' + input() + '#'))
field.append(['#'] * (W + 2))

dp = [[0 for _ in range(W+2)] for _ in range(H+2)]
dp[H][W] = 1

for i in range(H,0,-1):
    for j in range(W,0,-1):
        if field[i][j] == '#':
            continue
        else:
            dp[i][j] += dp[i][j+1] + dp[i+1][j]
        dp[i][j] %= MOD

print(dp[1][1])
### BUGGY CODE ###

def run(s, t):
    key_s = tuple(s)
    key_t = tuple(t)
    dic_s = {}
    dic_t = {}
    for key in key_s:
        dic_s[key] = s.count(key)
    for key in key_t:
        dic_t[key] = t.count(key)
    if sorted(dic_s.values()) == sorted(dic_t.values()):
        return 'Yes'
    else:
        return 'No'


def main():
    s = input()
    t = input()
    print(run(s, t))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import collections


def run(s, t):
    ss = sorted(list(collections.Counter(s).values()))
    tt = sorted(list(collections.Counter(t).values()))
    if ss == tt:
        return 'Yes'
    else:
        return 'No'


def main():
    s = input()
    t = input()
    print(run(s, t))


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

n,k=map(int,input().split())
s=[0]*n
a=list(map(int,input().split()))
for i in range(1,n):
    c=float("inf")
    for j in range(i-1,max(-1,i-1-k),-1):
        c=min(c,abs(a[i]-a[j])+s[j])
    else:
        s[i]=c
print(s[-1])

### FIXED CODE ###

n,k=map(int,input().split())
s=[0]*n
a=list(map(int,input().split()))
for i,h in enumerate(a):
    if i!=0:
        g=0 if i-k<0 else i-k
        s[i]=min([abs(h-d)+p for d,p in zip(a[g:i],s[g:i])])
print(s[-1])
### BUGGY CODE ###

import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

import numpy as np

R, C, K = rl()
#I = [[0]*(C+2) for _ in range(R+2)]
I = np.zeros((R+2, C+2), dtype=np.int)
for i in range(K):
	r, c, v = rl()
	I[r][c] = v
 
#dp = [[[0 for _ in range(C+2)] for _ in range(R+2)] for _ in range(4)]
dp = np.zeros((4,R+2,C+2), dtype=np.int)

for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[m][ni][nj] = max(dp[m][ni][nj], dp[m][i][j])
			if m < 3:
				dp[m+1][ni][nj] = max(dp[m+1][ni][nj], dp[m][i][j]+I[ni][nj])
			ni, nj = i+1, j
			dp[0][ni][nj] = max(dp[0][ni][nj], dp[m][i][j])
			dp[1][ni][nj] = max(dp[1][ni][nj], dp[m][i][j]+I[ni][nj])
ans = 0
for m in range(4):
	ans = max(ans, dp[m][R][C])
print(ans)


### FIXED CODE ###

import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)
 
R, C, K = rl()
I = [[0]*(C+2) for _ in range(R+2)]
for i in range(K):
	r, c, v = rl()
	I[r][c] = v
 
dp = [[0]*4 for _ in range(C+2)]
dp2 = [[0]*4 for _ in range(C+2)]
 
for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[nj][m] = max(dp[nj][m], dp[j][m])
			if m < 3:
				dp[nj][m+1] = max(dp[nj][m+1], dp[j][m]+I[ni][nj])
			ni, nj = i+1, j
			dp2[nj][0] = max(dp2[nj][0], dp[j][m])
			dp2[nj][1] = max(dp2[nj][1], dp[j][m]+I[ni][nj])
	dp = dp2
	dp2 = [[0]*4 for _ in range(C+2)]
ans = 0
for m in range(4):
	ans = max(ans, dp[C][m])
print(ans)
### BUGGY CODE ###

#!/usr/bin/python
# coding: UTF-8

def main():
    A,B,M = list(map(int, input().split(' ')))

    a_list = list(map(int, input().split(' ')))
    b_list = list(map(int, input().split(' ')))

    dic = {}
    for i in range(A):
        dic[i]={}
    for i in range(A):
        for j in range(B):
            dic[i][j] = 0


    x_y_c_list = []

    for i in range(M):
        temp = list(map(int, input().split(' ')))
        x_y_c_list.append(temp)

        if dic[temp[0]-1][temp[1]-1] == 0:
            dic[temp[0]-1][temp[1]-1] = temp[2]
        else:
            if dic[temp[0]-1][temp[1]-1] < temp[2]:
                dic[temp[0]-1][temp[1]-1] = temp[2]

    price_list = []
    for i in range(A):
        for j in range(B):
            price_list.append(a_list[i]+b_list[j] - dic[i][j])

    print(min(price_list))

if __name__=='__main__':
    main()


### FIXED CODE ###

#!/usr/bin/python
# coding: UTF-8

def main():
    A,B,M = list(map(int, input().split(' ')))

    a_list = list(map(int, input().split(' ')))
    b_list = list(map(int, input().split(' ')))


    price_list = 2*10**5
    for i in range(M):
        temp = list(map(int, input().split(' ')))
        if price_list > a_list[temp[0]-1] + b_list[temp[1]-1] - temp[2]:
            price_list = a_list[temp[0]-1] + b_list[temp[1]-1] - temp[2]

    lower = min(a_list) + min(b_list)
    if lower < price_list:
        print(lower)
    else:
        print(price_list)

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

N = int(input())
S = []
for i in range(N):
    S_tmp = str(input())
    S_tmp = list(S_tmp)
    S_tmp.sort()
    S.append("".join(S_tmp))

count=0
for i in range(len(S) - 1):
    for j in range(i+1, len(S)):
        if S[i]==S[j]:
            count+=1
print(count)

### FIXED CODE ###

import math

N = int(input())
S = []
for i in range(N):
    S_tmp = str(input())
    S_tmp = list(S_tmp)
    S_tmp.sort()
    S.append("".join(S_tmp))
S.sort()

count=0
x = 0
tmp = S[0]
count_all = []
for i in S[1:]:
    if tmp==i:
        count+=1
    else:
        if count>0:
            x += math.factorial(count+1)//(math.factorial(count+1-2) * math.factorial(2))
        count = 0
    tmp = i
if count>0:
    x += math.factorial(count+1)//(math.factorial(count+1-2) * math.factorial(2))
        
    tmp = i
print(x)
### BUGGY CODE ###

n,m=map(int,input().split())
G=[[] for i in range(n+1)]
flag=[1]*(n+1)
for i in range(m):
    x,y=map(int,input().split())
    G[x].append(y)
    flag[y]=0
# dp[i] node iからの最長パス
dp=[-1]*(n+1)
st=[]
for i in range(1,n+1):
    if flag[i]:
        st.append(i)
ans=0

def dfs(x):
    max_kyori=0
    dist=[-1]*(n+1)
    dist[x]=0
    stack=[x]
    while stack:
        a=stack.pop()
        kyori = dist[a]
        if G[a]!=[]:
            for t in G[a]:
                dist[t]=kyori+1
                max_kyori=max(max_kyori,kyori+1)
                stack.append(t)
    return max_kyori
kotae=0
for i in st:
    kotae=max(kotae,dfs(i))
print(kotae)

### FIXED CODE ###

import sys
input = sys.stdin.readline
#bfsするからdequeじゃないとだめ
from collections import deque
n,m=map(int,input().split())
infi=10**10
#topological sort
#通常のグラフ構成のグラフ
graph1=[[]for _ in range(n+1)]
#入ってくる辺の数を記録するグラフ
graph2=[ 0 for _ in range(n+1)]
for _ in range(m):
    x,y=map(int,input().split())
    graph1[x].append(y)
    graph2[y]+=1
#start地点になるのは入ってくる辺の数が0の点
start=deque([])
for i in range(1,n+1):
    if graph2[i]==0:
        start.append(i)
#start地点から
#①topoリストに加える
#②隣接点の入ってくる辺の数を減らす
#③入ってくる辺の数が0になったらstartに加える
#を繰り返す
#※今回はtopoに加えるのは本質ではない。
#topoに加えていく順序で見ていきながら距離を入れていく。
# topo=[]
dist=[infi]*(n+1)
for i in start:
    dist[i]=0
while start:
    a=start.popleft()
    kyori=dist[a]
#     topo.append(a)
    for b in graph1[a]:
        graph2[b]-=1
        if graph2[b]==0:
            start.append(b)
            dist[b]=min(dist[b],dist[a]+1)
print(max(dist[1:]))
### BUGGY CODE ###


import numpy as np

N,K,Q = map(int,input().split())
ps = [K]*N
ps = np.array(ps[:])

ac = []
for i in range(Q):
    an = int(input())
    ac.append(an)

for j in ac:
    ps = ps - 1
    ps[j-1] += 1
    
for k in ps:
    if k > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n, k, q = map(int, input().split())
n_score = [0] * n
for i in range(q):
    n_score[int(input()) - 1] += 1

for j in n_score:
    if k + j - q > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n=int(input())
s=int(n**0.5)
while True:
  if n%s==0:
    print(n//s+s-2)
    break
  s+=1

### FIXED CODE ###

n=int(input())
s=n**0.5
d=[]
for i in range(1,int(n**0.5)+1):
  if n%i==0:
    d.append(i)
    if i!=n//i:
      d.append(n//i)
d.sort()
import bisect as bi
b=bi.bisect_left(d,s)
print(min(n//d[b-1]+d[b-1]-2,n//d[b]+d[b]-2))
### BUGGY CODE ###

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

res = [1]*N
for _ in range(Q):
  t, d = input().split()
  for i in range(N):
    if t == S[i]:
      if d == "L":
        if i == 0:
          res[i] = 0
          break
        res[i-1] += res[i]
        res[i] = 0
      else:
        if i == N-1:
          res[i] = 0
          break
        res[i+1] += res[i]
        res[i] = 0
print(sum(res))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, Q = map(int,input().split())
S = "0"+input()+"0"
TD = [input().rstrip().split() for _ in range(Q)]
l, r = 0, N+1
for t, d in TD[::-1]:
  if t == S[l] and d == "R":
    l -= 1
  elif t == S[l+1] and d == "L":
    l += 1
  if t == S[r] and d == "L":
    r += 1
  elif t == S[r-1] and d == "R":
    r -= 1
print(max(0, r-l-1))
### BUGGY CODE ###

H = int(input())
l = [H]
c = 0
while l:
    h = l.pop()
    c += 1
    if h == 1:
        pass
    else:
        l.append(h//2)
        l.append(h//2)
print(c)

### FIXED CODE ###

H = int(input())
def rec(h):
    if h == 1:
        return 1
    else:
        return 1 + 2*rec(h//2)

print(rec(H))
### BUGGY CODE ###

from itertools import combinations as c
co = 0
r = range(1, int(input())+1)
s = "0" + input()
for i, j, k in c(r, 3):
  if s[i] != s[j] and s[j] != s[k] and s[k] != s[i] and j-i != k-j:
    co += 1
print(co)

### FIXED CODE ###

n, s = open(0)
r, g, b = map(s.count, "RGB")
e = enumerate
print(r*g*b - sum(f != g != s[i+j] != f for i, f in e(s) for j, g in e(s[i:-1:2])))
### BUGGY CODE ###

n, m, q = map(int,input().split())
bord = [[0 for _j in range(n+1)] for _i in range(n+1)]

for _i in range(m):
    left, right = map(int, input().split())
    bord[left][right] += 1
result = []
for _i in range(q):
    p, q = map(int, input().split())
    c = 0
    for i in range(p, q+1):
        for j in range(p, q+1):
            c += bord[i][j]
    result.append(c)
print(*result)

### FIXED CODE ###

n, m, q = map(int,input().split())
bord = [[0 for _j in range(n+2)] for _i in range(n+2)]

for _i in range(m):
    left, right = map(int, input().split())
    bord[left][right] += 1

for i in range(1, n+2):
    for j in range(1, n+2):
        bord[i][j] += bord[i][j-1]

result = []
for _i in range(q):
    p, q = map(int, input().split())
    c = 0
    for i in range(p, q+1):
        c += bord[i][q]-bord[i][p-1]
    result.append(c)
print(*result)
### BUGGY CODE ###

def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N)]
    if S[N-1] == '?':
        for m in range(10):
            dp[0][m] = 1
    else:
        tm = int(S[N-1])%13
        dp[0][tm] = 1
    for i in range(1,N):
        if S[-1-i] == '?':
            for j in range(13):
                for k in range(10):
                    dp[i][j] =(dp[i][j] + dp[i-1][(j-(k*10**i)%13)%13]) % MOD
        else:
            m = (int(S[N-1-i])*10**i) % 13
            for l in range(13):
                dp[i][l] = (dp[i][l] + dp[i-1][(l-m)%13]) % MOD
    print(dp[N-1][5]%MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] += 1
    s=[1]
    for n in range(1,N):
        s.append((s[n-1]*10)%13)
    for i in range(N):
        for k in range(13):
            if S[-(i+1)] != '?':
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] += dp[i][k] 
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] %= MOD
            else:
                for l in range(10):
                    dp[i+1][(k+l*s[i])%13] += dp[i][k]
                    dp[i+1][(k+l*s[i])%13] %= MOD
    print(dp[-1][5])

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

a=int(input())

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

sum=0

def pow_r(x, n):
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r(x ** 2, n // 2)
    else:  # standard case ② n is odd
        return x * pow_r(x ** 2, (n - 1) // 2)

for i in range(a-1):
  for j in range(i+1,a):
    sum=sum+d[i]*d[j]

print(sum%(pow_r(10,9)+7))

### FIXED CODE ###

MOD = 10 ** 9 + 7

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

total=sum(alst)
sum=0

# for i in range(n-1):
#   for j in range(i+1,n):
#     sum=pow(sum+alst[i]*alst[j],1,MOD)

# print(sum)

for a in alst:
  sum = sum+a * (total - a)
  sum %= MOD

sum *= pow(2, MOD - 2, MOD)
sum %= MOD
print(sum)
### BUGGY CODE ###

import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    As = list(map(int, input().split()))
    #print(As)
    #print([As.index(i+1)+1 for i in range(N)])
    ans = " ".join([str(As.index(i+1)+1) for i in range(N)])
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import numpy as np
def main():
    input = sys.stdin.readline
    N = int(input())
    As = list(map(int, input().split()))
    ans = " ".join(list((np.argsort(As)+1).astype("str")))
    print(ans)

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

N,C=[int(x) for x in str(input()).split()]
D=[[0 for x in range(0,C+1)]]
for i in range (0,C):
  D.append([0]+[int(x) for x in str(input()).split()])
c=[[0 for x in range(0,N+1)]]
for j in range(0,N):
  c.append([0]+[int(x) for x in str(input()).split()])


error=1000000000
for i in range(1,C+1):
  for j in range(1,C+1):
    if j!=i:
      for k in range(1,C+1):
        if k!=j:
          if k!=i:
            
            e=0
            for x in range(1,N+1):
              for y in range(1,N+1):
                
                if (x+y)%3==0:
                  e+=D[c[x][y]][i]
                elif (x+y)%3==1:
                  e+=D[c[x][y]][j]
                elif (x+y)%3==2:
                  e+=D[c[x][y]][k]
                if e>error:
                  break
       
            error=min(error,e)
print(error)





### FIXED CODE ###

N,C=[int(x) for x in str(input()).split()]
D=[[0 for x in range(0,C+1)]]
for i in range (0,C):
  D.append([0]+[int(x) for x in str(input()).split()])
c=[[0 for x in range(0,N+1)]]
for j in range(0,N):
  c.append([0]+[int(x) for x in str(input()).split()])



mod1=[0 for x in range(0,C+1)]
mod2=[0 for x in range(0,C+1)]
mod0=[0 for x in range(0,C+1)]

for x in range (1,N+1):
  for y in range(1,N+1):
    if (x+y)%3==0:
      mod0[c[x][y]]+=1
    elif (x+y)%3==1:
      mod1[c[x][y]]+=1
    else:
      mod2[c[x][y]]+=1



error=1000000000
for i in range(1,C+1):
  for j in range(1,C+1):
    if j!=i:
      for k in range(1,C+1):
        if k!=j:
          if k!=i:
            e=0

            for x in range(1,C+1):
              e+=mod0[x]*D[x][i]+mod1[x]*D[x][j]+mod2[x]*D[x][k]


       
            error=min(error,e)
print(error)
### BUGGY CODE ###

h,w=map(int,input().split())
s = [[0]*w for _ in range(h)]
for i in range(h):
    s[i] = list(*input().split())

def cango(now,h,w):
    ans = []
    if now[0]>0:
        ans.append( (now[0]-1,now[1]) )
    if now[0]<h-1:
        ans.append( (now[0]+1,now[1]) )
    if now[1]>0:
        ans.append( (now[0],now[1]-1) )
    if now[1]<w-1:
        ans.append( (now[0],now[1]+1) )
    return ans

from collections import deque

ans=0
for hh in range(h):
    for ww in range(w):
        if s[hh][ww]==".":
            start = (hh,ww)
            q = deque( [] )
            q.append( ((-1,-1),start,0) )
            visit = [[0]*w for _ in range(h)]
            while q:
                old,now,dist = q.popleft()
                visit[now[0]][now[1]] = 1
#                 print(old,now,dist)
                if ans<dist:
                    ans=dist
                for new in cango(now,h,w):
                    if s[new[0]][new[1]]=="." and visit[new[0]][new[1]]==0:
                        q.append( (now,new,dist+1) )
print(ans )
    

### FIXED CODE ###

h,w=map(int,input().split())
s = [[0]*w for _ in range(h)]
for i in range(h):
    s[i] = list(*input().split())

def cango(now,h,w):
    ans = []
    if now[0]>0:
        ans.append( (now[0]-1,now[1]) )
    if now[0]<h-1:
        ans.append( (now[0]+1,now[1]) )
    if now[1]>0:
        ans.append( (now[0],now[1]-1) )
    if now[1]<w-1:
        ans.append( (now[0],now[1]+1) )
    return ans

from collections import deque

ans=0
for hh in range(h):
    for ww in range(w):
        if s[hh][ww]==".":
            start = (hh,ww)
            q = deque( [] )
            q.append( ((-1,-1),start,0) )
            visit = [[0]*w for _ in range(h)]
            visit[hh][ww]=1
            while q:
                old,now,dist = q.popleft()
#                 print(old,now,dist)
                if ans<dist:
                    ans=dist
                for new in cango(now,h,w):
                    if s[new[0]][new[1]]=="." and visit[new[0]][new[1]]==0:
                        q.append( (now,new,dist+1) )
                        visit[new[0]][new[1]] = 1
print(ans )
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(3)]
ps = sorted([a + b for a in ls[0] for b in ls[1]], reverse=True)[:k]
res = sorted([ab + c for ab in ps for c in ls[2]], reverse=True)[:k]
print(*res, sep='\n')

### FIXED CODE ###

import heapq


def select(ls0, ls1, k):
    ls = []
    for a in ls0:
        for b in ls1:
            heapq.heappush(ls, -(a + b))
    return [-heapq.heappop(ls) for _ in range(min(k, len(ls0) * len(ls1)))]


x, y, z, k = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(3)]
for i in range(3):
    ls[i].sort(reverse=True)
ps = select(ls[0], ls[1], k)
res = select(ps, ls[2], k)
print(*res, sep='\n')
### BUGGY CODE ###

N, K = map(int,input().split())
h = list(map(int,input().split()))
dp = [float("inf")]*(N)
dp[0] = 0

for i in range(1,N):
    now = h[i]
    dp[i] = min([abs(now-h[j])+dp[j] for j in range(max(i-K,0),i)])

print(dp[N-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]*(N)

for i in range(1,N):
    now = h[i]
    dp[i] = min([abs(now-h[j])+dp[j] for j in range(max(i-K,0),i)])

print(dp[N-1])
### BUGGY CODE ###

n=int(input())
p = list(map(int,input().split()))
# print(p)
min=300000
ans=0

for i in range(n):
    if i == 0:
        ans+=1
        continue

    for j in range(i):
        # print(p[i],p[j],i,j)
        if p[i] > min:
            break
        elif p[i] < min:
            min = p[i]
        if p[i] > p[j]:
            break
        elif j == i-1:
            ans+=1

print(ans)


### FIXED CODE ###

n=int(input())
p = list(map(int,input().split()))
# print(p)
min=p[0]
ans=0

for i in range(n):
    if i == 0:
        ans+=1
        continue
    if p[i] > min:
        continue
    if p[i] < min:
        min=p[i]
        ans+=1

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

from collections import Counter
import math
def solve():
    N = int(input())
    A = list(map(int,input().split()))

    st = set(A)
    counter = Counter(A)

    ans = 0
    for i in range(N):
        if counter[A[i]] >= 2:
            continue

        res = calc_divisors(A[i],st)
        if res:
            ans += 1
    
    print(ans)

def calc_divisors(n,st):
    res = False
    for i in range(1,int(math.sqrt(n)+1)):
        if n % i == 0:
            res = func(i,st,n)
            if res:
                return False
            
            if (i*i != n):
                res = func(n//i,st,n)
        
        if res:
            return False

    return True

def func(i,st,n):
    if i == n:
        return False
    if i in st:
        return True
    else:
        return False

if __name__ == '__main__':
    solve()

### FIXED CODE ###

from collections import Counter
def solve():
    N = int(input())
    A = list(map(int,input().split()))
    dp = [True] * (10 ** 6 + 1)
    counter = Counter(A)

    A.sort()
    ans = 0
    for a in A:
        if dp[a]:
            if counter[a] == 1:
                ans += 1
            i = a
            while i <= 10 ** 6:
                dp[i] = False
                i += a
    
    print(ans)

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

N,A=map(int,input().split())
X=[int(a) for a in input().split()]
X.insert(0,0)
ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
dp=[[[0 for i in range(N*50+1)] for j in range(N+1)] for k in range(N+1)]
for i in range(N+1):
  dp[i][0][0]=1
for i in range(1,N+1):
  for j in range(1,N+1):
    for k in range(ma+1):
      if k < X[i]:
        dp[i][j][k]=dp[i-1][j][k]
      else:
        dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-X[i]]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
ans=0
for x in range(1,N+1):
  if x*A<=ma:
    ans+=dp[N][x][x*A]
print(ans)


### FIXED CODE ###

def solve(N,A,X):  
  X.append(0)
  X.sort()
  ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
  dp=[[[0] * (ma+1) for _ in range(N+1)] for _ in range(N+1)]
  
#[x]までの0個を使って0を作る方法は1つ（dp初期化）
  for i in range(N+1):
    dp[i][0][0]=1
  for i in range(1,N+1):
    cnt=X[i]
    for j in range(1,N+1):
      for k in range(ma+1):
        if k < cnt:
          dp[i][j][k]=dp[i-1][j][k]
        else:
          dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-cnt]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
  ans=0
  for x in range(1,N+1):
    if x*A<=ma:
      ans+=dp[N][x][x*A]
  return ans

N,A=map(int,input().split())
X=[int(a) for a in input().split()]
ans=solve(N,A,X)
print(ans)