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

s=input()
t=input()
ls=len(s)
lt=len(t)
dp=[[""]*(lt+1) for i in range(ls+1)]
for i in range(ls):
  for j in range(lt):
    if len(dp[i+1][j])==max(len(dp[i][j+1]),len(dp[i+1][j]),len(dp[i][j])+(s[i]==t[j])):
      dp[i+1][j+1]=dp[i+1][j]
    elif len(dp[i][j+1])==max(len(dp[i][j+1]),len(dp[i+1][j]),len(dp[i][j])+(s[i]==t[j])):
      dp[i+1][j+1]=dp[i][j+1]
    else:
      dp[i+1][j+1]=dp[i][j]+s[i]
print(dp[ls][lt])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
s=input()
t=input()
ls=len(s)
lt=len(t)
dp=[[0]*(lt+1) for i in range(ls+1)]
for i in range(ls):
  for j in range(lt):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1
    else:
      dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
                                                                                                    
ans=""
def rec(i,j):
  if i==0 or j==0:
    return 
  global ans
  if s[i-1]==t[j-1]:
    ans+=s[i-1]
    rec(i-1,j-1)
  elif dp[i-1][j]>=dp[i][j-1]:
    rec(i-1,j)
  else:
    rec(i,j-1)
rec(ls,lt)
print(ans[::-1])
### BUGGY CODE ###

import itertools
X,Y,Z,K=[int(i) for i in input().split(" ")]
A=[int(i) for i in input().split(" ")]
B=[int(i) for i in input().split(" ")]
C=[int(i) for i in input().split(" ")]

AB=[]

A=sorted(A,reverse=True)[:K:]
B=sorted(B,reverse=True)[:K:]
C=sorted(C,reverse=True)[:K:]
for i in itertools.product(A,B):
    a,b=i
    AB.append(a+b)

AB=sorted(AB,reverse=True)[:K:]

ABC=[]
for i in itertools.product(AB,C):
    ab,c=i
    ABC.append(ab+c)

ABC=sorted(ABC,reverse=True)[:K:]


for abc in ABC:
    print(abc)


### FIXED CODE ###

import heapq
X,Y,Z,K=[int(i) for i in input().split(" ")]
A=[int(i) for i in input().split(" ")]
B=[int(i) for i in input().split(" ")]
C=[int(i) for i in input().split(" ")]

AB=[]
for a in A:
    for b in B:
        AB.append(a+b)

AB=heapq.nlargest(K,AB)
ABC=[]
for ab in AB:
    for c in C:
        ABC.append(ab+c)

for cake in heapq.nlargest(K,ABC):
    print(cake)
### BUGGY CODE ###

s = input()
s = s[::-1]
mod = 10 ** 9 + 7
table = [[0] * 13 for _ in range(len(s) + 2)]
table[0][0] = 1
dd = 1
for c in range(len(s)):
    dd = (10 ** c) % 13
    if s[c] == "?":
        for n in range(10):
            for i in range(13):
                table[c + 1][(i + n * dd) % 13] += table[c][i]
    else:
        num = int(s[c])
        for i in range(13):
            table[c + 1][(i + num * dd) % 13] += table[c][i]

print(table[c + 1][5] % mod)

### FIXED CODE ###

s = input()
s = s[::-1]
mod = 10 ** 9 + 7
table = [[0] * 13 for _ in range(len(s) + 2)]
table[0][0] = 1
dd = 1
for c in range(len(s)):
    if s[c] == "?":
        for n in range(10):
            for i in range(13):
                table[c + 1][(i + n * dd) % 13] += table[c][i]
                table[c + 1][(i + n * dd) % 13] %= mod
    else:
        num = int(s[c])
        for i in range(13):
            table[c + 1][(i + num * dd) % 13] += table[c][i]
            table[c + 1][(i + num * dd) % 13] %= mod
    dd = (dd * 10) % 13
print(table[c + 1][5])
### BUGGY CODE ###

n = int(input())
s = str(input())
r = []
g = []
for i in range(n):
    if s[i] == "R":
        r.append(i)
    elif s[i] == "G":
        g.append(i)
ans = len(r)*len(g)*(n-(len(r)+len(g)))
for i in range(len(r)):
    for j in range(len(g)):
        if max(r[i],g[j])+(abs(r[i]-g[j])) < n:
            if s[max(r[i],g[j])+(abs(r[i]-g[j]))] == "B":
                ans -= 1
        if 0 <= min(r[i],g[j])-(abs(r[i]-g[j])):
            if s[min(r[i],g[j])-(abs(r[i]-g[j]))] == "B":
                ans -= 1
        if abs(r[i]-g[j])%2 == 0:
            if s[(r[i]+g[j])//2] == "B":
                ans -= 1
print(ans)

### FIXED CODE ###

n = int(input())
s = str(input())
r = []
g = []
def right(r,g):
    return (max(r,g)+(abs(r-g)))
def left(r,g):
    return (min(r,g)-(abs(r-g)))
def half(r,g):
    return ((r+g)//2)
for i in range(n):
    if s[i] == "R":
        r.append(i)
    elif s[i] == "G":
        g.append(i)
ans = len(r)*len(g)*(n-(len(r)+len(g)))
for i in range(len(r)):
    for j in range(len(g)):
        t = left(r[i],g[j])
        f = right(r[i],g[j])
        h = half(r[i],g[j])
        if f < n:
            if s[f] == "B":
                ans -= 1
        if 0 <= t:
            if s[t] == "B":
                ans -= 1
        if abs(r[i]-g[j])%2 == 0:
            if s[h] == "B":
                ans -= 1
print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
ans = 0
d = {}
if len(l) == len(set(l)):
  for i in range(len(l)):
    print(0)
else:
  for s in l:
    if s not in d:
      d[s] = 1
    else:
      d[s] += 1
  for i in range(n):
    ans = 0
    for j,k in d.items():
      if l[i] == j and k >= 2:
        ans += (k-1)*(k-2)//2
      else:
        ans += k*(k-1)//2
    print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
ans = 0
ansl = 0
d = {}
if len(l) == len(set(l)):
  for i in range(len(l)):
    print(0)
else:
  for s in l:
    if s not in d:
      d[s] = 1
    else:
      d[s] += 1
  for j,k in d.items():
    ans += k*(k-1)//2
  ansl = ans
  for i in range(n):
    ans = ansl
    x = d[l[i]]
    ans -= x - 1
    print(ans)
### BUGGY CODE ###

import bisect

N = int(input())
L = int(''.join([str(n) for n in range(1, N+1)]))
R = int(''.join([str(n) for n in range(1, N+1)][::-1]))

P = int(''.join(input().split()))
Q = int(''.join(input().split()))

C = [str(c) for c in range(1, N+1)]
A = []
for i in range(L, R+1):
    flg = True
    for c in C:
        if c not in str(i):
            flg = False
            break
    if flg:
        A.append(i)
print(abs(bisect.bisect(A, P)-bisect.bisect(A, Q)))


### FIXED CODE ###

from itertools import permutations

N = int(input())
P = tuple(int(n) for n in input().split())
Q = tuple(int(n) for n in input().split())

a = [x for x in permutations(range(1,N+1), N)]

print(abs(a.index(P)-a.index(Q)))
### BUGGY CODE ###

N = int(input())
s = 0
for i in range(1,N):
    s = s + divmod(i,i+1)[1]
s = s + divmod(N,1)[1]
print(s)

### FIXED CODE ###

N = int(input())
print((N-1)*N//2)
### BUGGY CODE ###

from math import factorial
import collections

N = int(input())
A = input().split()
A = [int(x) for x in A]

L = collections.Counter(A)

L = L.most_common()

c = 0
for z in L:
    if z[1] >=2:
        c += factorial(z[1]) // factorial(2) // factorial(z[1] - 2)

for k in range(N):
    c1 = c
    x = A[k]
    for z in L:
        if z[0] == x and z[1] >= 2:
            c1 -= factorial(z[1]) // factorial(2) // factorial(z[1] - 2)
            if z[1]-1 >= 2:
                c1 += factorial(z[1]-1) // factorial(2) // factorial(z[1]-1 - 2)
    print(c1)

### FIXED CODE ###

from math import factorial
import collections

N = int(input())
A = input().split()
A = [int(x) for x in A]

L = collections.Counter(A)

c = 0
for i in range(1,N+1):
    n = L[i]
    if n >=2:
        c += factorial(n) // factorial(2) // factorial(n - 2)

for k in range(N):
    c1 = c
    n = L[A[k]]
    if n >= 3:
        c1 -= n-1
    elif n == 2:
        c1 -= factorial(n) // factorial(2) // factorial(n-2)
    print(c1)
### BUGGY CODE ###

t = input('')

def check_score(s):    
    s1 = s.count('PD')
    s2 = s.count('D')
    return s1+s2

# ?の位置を調査
tlist = list(t)
qlist = []
for i in range(len(tlist)):
    if tlist[i] == '?':
        qlist.append(i)

n=len(qlist)
max_s = ''
max_c = 0
for i in range(2**n):
    tlist = list(t)
    s=''
    for j in range(n):
        idx = qlist[j]
        if ((i>>j) &1):
            tlist[idx] = 'P'
        else:
            tlist[idx] = 'D'
    st = "".join(tlist)
    score = check_score(st)
#    print("{}:{}".format(st,score))
    if score > max_c:
        max_c = score
        max_s = st

print("{}".format(max_s))

### FIXED CODE ###

t = input('')

tlist = list(t)
for i in range(len(tlist)):
    if tlist[i] == '?':
        if i==0:
            tlist[i] = 'D'
        elif i==len(tlist)-1:
            tlist[i] = 'D'
        else:
            if tlist[i-1] == 'P':
                if tlist[i+1] == 'P':
                    tlist[i] = 'D'
                elif tlist[i+1] == 'D':
                    tlist[i] = 'D'
                elif tlist[i+1] == '?':
                    tlist[i] = 'D'
            else:
                # 1つ前が'D'
                if tlist[i+1] == 'P':
                    tlist[i] = 'D'
                elif tlist[i+1] == 'D':
                    tlist[i] = 'P'
                elif tlist[i+1] == '?':
                    tlist[i] = 'P'

print("".join(tlist))
### BUGGY CODE ###

N,K=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(N-1)]
graph=[[] for _ in [0]*N]
for a,b in ab:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
info=[[False,set(),set(),-1] for _ in [0]*N]
q=[[0,""]]
while(q):
    i,j = q.pop()
    if j!="":
        info[i][1].add(j)
        [info[i][2].add(k) for k in info[j][1]]
    if info[i][0]==False:
        info[i][0]=True
        info[i][3]=K-len(info[i][1])-len(info[i][2])
    while(graph[i]):
        g=graph[i].pop()
        q.append((g,i))
ans=1
mod=10**9+7
for i in info:
    ans=(ans*i[3])%mod
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(N-1)]
graph=[[] for _ in [0]*N]
[graph[a-1].append(b-1) for a,b in ab]
[graph[b-1].append(a-1) for a,b in ab]
q=[[-1,0]]
cnt=0
ans=K
mod=10**9+7
while(q):
    q1=[]
    if cnt<2:
        cnt+=1
    for i,j in q:
        g=graph[j]
        if i!=-1:
            g.remove(i)
        for cnt2,k in enumerate(g):
            q1.append([j,k])
            ans=(ans*(K-cnt-cnt2))%mod
    q=q1
print(ans)
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
a=0
for i in range(3001):
    for j in range(3001):
        if (n-(r*i+g*j))%b==0 and (n-(r*i+g*j))>=0:
            a+=1
print(a)

### FIXED CODE ###

r,g,b,n=map(int,input().split())
a=0
for i in range(3001):
    for j in range(3001):
        if (n-(r*i+g*j))%b==0 and (n-(r*i+g*j))>=0:
            a+=1
print(a)
### BUGGY CODE ###

#input
N, Q = [int(i) for i in input().split(" ")]
st = input()
lis = []
for i in range(Q):
  lis.append([int(i) for i in input().split(" ")])
  
for i in range(Q):
  print(st[lis[i][0]-1:lis[i][1]].count("AC"))

### FIXED CODE ###

from itertools import accumulate


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

flg = []
for i in range(N-1):
    tmp_S = S[i:i+2]
    if tmp_S == 'AC':
        flg.append(1)
    else:
        flg.append(0)

flg2 = [0] + flg
flg2 = list(accumulate(flg2))

for a in A:
    print(flg2[a[1]-1] - flg2[a[0]-1])
### BUGGY CODE ###

s = input()
t = input()

l = len(s)
d = dict()
for i in range(l):
    if s[i] in d.keys():
        d[s[i]].append(i+1)
    else:
        d[s[i]] = [i+1]

ans = 0
now = 0
for i in t:
    if i not in d.keys():
        print(-1)
        exit()

    for j in d[i]:
        if j > now:
            now = j
            break
    else:
        now = d[i][0]
        ans += l

print(ans + now)


### FIXED CODE ###

import bisect
s = input()
t = input()

l = len(s)
d = dict()
for i in range(l):
    if s[i] in d.keys():
        d[s[i]].append(i+1)
    else:
        d[s[i]] = [i+1]

ans = 0
now = 0
for i in t:
    if i not in d.keys():
        print(-1)
        exit()

    a = bisect.bisect_right(d[i], now)
    if a == len(d[i]):
        now = d[i][0]
        ans += l
    else:
        now = d[i][a]

print(ans + now)
### BUGGY CODE ###

n = int(input())
s = list(map(int, input().split()))
c = 0
a = 'a'
def merge(A, left, mid, right):
    global c
    L = A[left:mid]
    R = A[mid:right]
    L.append(10 ** 9)
    R.append(10 ** 9)
    i = 0
    j = 0
    for k in range(left, right):
        c += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def mergesort(A, left, right):
    if left+1 < right:
        mid = (left+right)//2
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, mid, right)
        return A

ans = mergesort(s, 0, n)

for i in ans:
    a = str(a) + str(i) + ' '
print(a[1:-1])
print(c)


### FIXED CODE ###

import sys
n = int(input())
s = list(map(int, input().split()))
c = 0
a = 'a'
def merge(A, left, mid, right):
    global c
    L = A[left:mid]
    R = A[mid:right]
    L.append(sys.maxsize)
    R.append(sys.maxsize)
    i = 0
    j = 0
    for k in range(left, right):
        c += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def mergesort(A, left, right):
    if left+1 < right:
        mid = (left+right)//2
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, mid, right)

mergesort(s, 0, n)

for i in range(n-1):
    print(s[i], end=' ')
print(s[n-1])
print(c)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
B = np.cumsum(A)
cnt = 0
for k in range(N):
  cnt += (B[k:] == 0).sum()
  B -= A[k]
print(cnt)

### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array([0] + list(map(int, input().split())))
B = np.cumsum(A)
B.sort()
cnt = 1
out = 0
for k in range(N):
  if B[k] == B[k+1]:
    cnt += 1
    if k == N-1:
      out += (cnt * (cnt - 1)) // 2
  else:
    out += (cnt * (cnt - 1)) // 2
    cnt = 1
print(out)
### BUGGY CODE ###

from itertools import combinations
n = int(input())
s = list(input())
a = list(combinations(s,3))
b = set(a)
print (len(b))

### FIXED CODE ###

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

a = ["0","1","2","3","4","5","6","7","8","9"]

c = 0

for i in a:
	for j in a:
		for k in a:
			d = s.find(i)
			if d == -1:
				continue
			e = s[d+1:].find(j)
			if e == -1:
				continue
			e += d+1
			f = s[e+1:].find(k)
			if f == -1:
				continue
			c += 1
print (c)
### BUGGY CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
pq = []
for i in range(n):
    pq.append((-a[i], -a[i], 0))
heapq.heapify(pq)
for i in range(m):
    mx = heapq.heappop(pq)
    if -mx[1] < (2 ** (mx[2] + 1)): heapq.heappush(pq, (0, mx[1], mx[2] + 1))
    else: heapq.heappush(pq, (-(-mx[1] // (2 ** (mx[2] + 1))), mx[1], mx[2] + 1))
ans = 0
while len(pq) != 0:
    ans -= heapq.heappop(pq)[0]
print(ans)
"""
import heapq
a = [(3, 0), (1, 0), (2, 2), (6, 4)]
#listのheap化
#heapはsortではないので順番は割とあべこべになる。最小値は先頭
heapq.heapify(a)
print(a)

#挿入
heapq.heappush(a, (3, 3))
print(a)

#最小値を削除&出力
print(heapq.heappop(a))
print(a)
"""

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
pq = []
for i in range(n):
    pq.append((-a[i], -a[i], 0))
heapq.heapify(pq)
for i in range(m):
    if len(pq) == 0: break
    mx = heapq.heappop(pq)
    if -mx[1] >= (2 ** (mx[2] + 1)): heapq.heappush(pq, (-(-mx[1] // (2 ** (mx[2] + 1))), mx[1], mx[2] + 1))
ans = 0
while len(pq) != 0:
    ans -= heapq.heappop(pq)[0]
print(ans)
### BUGGY CODE ###

# ABC122C - GeT AC
import sys
input = sys.stdin.readline

n, q = list(map(int, input().rstrip().split()))
s = input().rstrip()
arr = [list(map(int, input().rstrip().split())) for _ in range(q)]
cnt = [0] * (n - 1)
for c, (i, j) in enumerate(zip(s, s[1:])):
    if i + j == "AC":
        cnt[c] += 1
for i, j in arr:
    print(cnt[i - 1 : j - 1].count(1))

### FIXED CODE ###

# ABC122C - GeT AC
import sys
input = sys.stdin.readline

n, q = list(map(int, input().rstrip().split()))
s = input().rstrip()
arr = [list(map(int, input().rstrip().split())) for _ in range(q)]
cnt = [0] * (n + 1)
for i in range(n):
    if s[i : i + 2] == "AC":
        cnt[i + 1] = cnt[i] + 1
    else:
        cnt[i + 1] = cnt[i]
for i, j in arr:
    print(cnt[j - 1] - cnt[i - 1])
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1,N+1):
    for j in range(1,N+1):
        if i % j == 0:
            ans+=i
print(ans)


### FIXED CODE ###

N = int(input())
ans = 0
for j in range(1,N+1):
    Y = N//j
    ans += Y*(Y+1)*j//2
print(ans)
### BUGGY CODE ###

import collections

n=int(input())

li=[]
ma=0
an=[]

for i in range(n):
    li.append(input())

c=collections.Counter(li)
ma=c.most_common()[0][1]


for j in range(n):
    if c.most_common()[j][1]==ma:
        an.append(c.most_common()[j][0])
        
        if len(c)==j+1:
            break
    else:
        break

an.sort()

for k in range(len(an)):
    print(an[k])

### FIXED CODE ###

n=int(input())

li={}
an=[]
ma=0

for i in range(n):
    t=input()
    if t in li:
        li[t]+=1
    else:
        li[t]=1

li2=sorted(li.items(), key=lambda x:x[1],reverse=True)

ma=li2[0][1]

for j in range(n):
    if li2[j][1]==ma:
        an.append(li2[j][0])
        
        if len(li2)==j+1:
            break
    else:
        break

an.sort()
 
for k in range(len(an)):
    print(an[k])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n,k=map(int,input().split())
vr,vs,vp=map(int,input().split())
t=list(input())

rr=0
ss=1
pp=2

vsum=0
for i in range(k):
    ti=[t[ii] for ii in range(n) if ii%k==i]
    ni=len(ti)
#    dp=[[0]*3 for i in range(ni+1)]
    dpir=0
    dpis=0
    dpip=0
    for i2 in range(ni):
        if ti[i2]=="r":
#            dp[i2+1][rr]=max(dp[i2][ss],dp[i2][pp])
#            dp[i2+1][ss]=max(dp[i2][pp],dp[i2][rr])
#            dp[i2+1][pp]=max(dp[i2][rr]+vp,dp[i2][ss]+vp)
            dpir2=max(dpis,dpip)
            dpis2=max(dpip,dpir)
            dpip2=max(dpir,dpis)+vp
        elif ti[i2]=="s":
#            dp[i2+1][rr]=max(dp[i2][ss]+vr,dp[i2][pp]+vr)
#            dp[i2+1][ss]=max(dp[i2][pp],dp[i2][rr])
#            dp[i2+1][pp]=max(dp[i2][rr],dp[i2][ss])
            dpir2=max(dpis,dpip)+vr
            dpis2=max(dpip,dpir)
            dpip2=max(dpir,dpis)
        elif ti[i2]=="p":
#            dp[i2+1][rr]=max(dp[i2][ss],dp[i2][pp])
#            dp[i2+1][ss]=max(dp[i2][pp]+vs,dp[i2][rr]+vs)
#            dp[i2+1][pp]=max(dp[i2][rr],dp[i2][ss])
            dpir2=max(dpis,dpip)
            dpis2=max(dpip,dpir)+vs
            dpip2=max(dpir,dpis)
        dpir=dpir2
        dpis=dpis2
        dpip=dpip2
#    vsum+=max(dp[ni][rr],dp[ni][ss],dp[ni][pp])
    vsum+=max(dpir,dpis,dpip)
print(vsum)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n,k=map(int,input().split())
vr,vs,vp=map(int,input().split())
t=list(input())

rr=0
ss=1
pp=2

vsum=0
for i in range(k):
#    ti=[t[ii] for ii in range(n) if ii%k==i]
#    ni=len(ti)
#    dp=[[0]*3 for i in range(ni+1)]
    dpir=0
    dpis=0
    dpip=0
    for i2 in range(i,n,k):
        if t[i2]=="r":
#            dp[i2+1][rr]=max(dp[i2][ss],dp[i2][pp])
#            dp[i2+1][ss]=max(dp[i2][pp],dp[i2][rr])
#            dp[i2+1][pp]=max(dp[i2][rr]+vp,dp[i2][ss]+vp)
            dpir2=max(dpis,dpip)
            dpis2=max(dpip,dpir)
            dpip2=max(dpir,dpis)+vp
        elif t[i2]=="s":
#            dp[i2+1][rr]=max(dp[i2][ss]+vr,dp[i2][pp]+vr)
#            dp[i2+1][ss]=max(dp[i2][pp],dp[i2][rr])
#            dp[i2+1][pp]=max(dp[i2][rr],dp[i2][ss])
            dpir2=max(dpis,dpip)+vr
            dpis2=max(dpip,dpir)
            dpip2=max(dpir,dpis)
        elif t[i2]=="p":
#            dp[i2+1][rr]=max(dp[i2][ss],dp[i2][pp])
#            dp[i2+1][ss]=max(dp[i2][pp]+vs,dp[i2][rr]+vs)
#            dp[i2+1][pp]=max(dp[i2][rr],dp[i2][ss])
            dpir2=max(dpis,dpip)
            dpis2=max(dpip,dpir)+vs
            dpip2=max(dpir,dpis)
        dpir=dpir2
        dpis=dpis2
        dpip=dpip2
#    vsum+=max(dp[ni][rr],dp[ni][ss],dp[ni][pp])
    vsum+=max(dpir,dpis,dpip)
print(vsum)
### BUGGY CODE ###

n,a = map(int,input().split())
lst = [int(i) for i in input().split()]
lst.sort()


ans = 0
for i in range(2 ** n):
    bit = format(i,'b')
    bit = bit.rjust(n,'0')
    lcs = 0
    cnt = 0
    for w in range(n):
        if bit[w]=='1':
            lcs += lst[w]
            cnt += 1
    
    if cnt != 0:
        if lcs / cnt == a:
            ans += 1

print(ans)

### FIXED CODE ###

num,ave = map(int,input().split())
numx = list(map(int,input().split()))

L = len(numx)
numy = [0] * L
for i in range(L):
    numy[i] = numx[i] - ave

if abs(min(numy)) < abs(max(numy)):
    maxX = max(numy)
else:
    maxX = abs(min(numy))

dp = [[0]*(2*maxX*L+1) for _ in range(L+1)]
dp[0][maxX*L] = 1
for i in range(L):
    for j in range(2*maxX*L+1):
        if (j-numy[i]) < 0 or (j - numy[i]) > 2*maxX*L:
          dp[i+1][j] = dp[i][j]
        else:
          dp[i+1][j] = dp[i][j] + dp[i][j-numy[i]]
print(dp[L][maxX*L]-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
mod = 2019
s = input().rstrip()
n = len(s)
mod_list = []
for i in range(n):
    s_ = s[i:]
    mod_list.append(int(s_) % mod)
mod_list.append(0)
from collections import Counter
c = Counter(mod_list)
ans = 0
for i in c.keys():
    ans += c[i] * (c[i] - 1) // 2
print(ans)





### FIXED CODE ###

import sys
input = sys.stdin.readline

mod = 2019

s = input().rstrip()
n = len(s)

t = [int(s[n - 1])]

mul = 10
for i in range(n - 2, -1, -1):
    t.append((t[-1] + int(s[i])*mul) % mod)
    mul *= 10
    mul %= mod
t.append(0)

from collections import Counter

c = Counter(t)
ans = 0

for i in c.keys():
    ans += c[i]*(c[i] - 1) // 2

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

import sys

n,m=map(int,input().split())
a=[]
b=[]
for i in range(m):
	numa,numb=map(int,input().split())
	a.append(numa)
	b.append(numb)
bb=[]
if not 1 in a or not n in b:
	print("IMPOSSIBLE")
	sys.exit()
for j in range(len(a)):
    if 1==a[j]:
        bb.append(b[j])
if len(bb)==0:
	print("IMPOSSIBLE")
	sys.exit()
for k in range(len(bb)):
	for l in range(len(a)):
		if bb[k]==a[l] and b[l]==n :
			print("POSSIBLE")
			sys.exit()
print("IMPOSSIBLE")

### FIXED CODE ###

import sys

n,m=map(int,input().split())
a=[]
b=[]
for i in range(m):
	numa,numb=map(int,input().split())
	a.append(numa)
	b.append(numb)
bb=[]
aa=[]
if not 1 in a or not n in b:
	print("IMPOSSIBLE")
	sys.exit()
for j in range(len(a)):
    if 1==a[j]:
        bb.append(b[j])
for k in range(len(b)):
    if n==b[k]:
        aa.append(a[k])
list=set(aa) & set(bb)
print("IMPOSSIBLE" if len(list)==0 else "POSSIBLE")
### BUGGY CODE ###

S=input()
mc=[0]*2019

tg=0
digit=1
for s in S[::-1]:
    tg+=int(s)*digit
    mc[tg%2019]+=1
    digit*=10%2019

ans=sum(m*(m-1)//2 for m in mc)
print(ans+mc[0])


### FIXED CODE ###

S=input()
mc=[0]*2019

tg=0
digit=1
for s in S[::-1]:
    tg+=int(s)*digit
    mc[tg%2019]+=1
    digit=digit*10%2019

ans=sum(m*(m-1)//2 for m in mc)
print(ans+mc[0])