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

N,M=input().split()
N =int(N)
M =int(M)
a= []
a= list(int(_) for _ in input().split())
dict={}
ans = 0
for i in range(N+1):
    p = sum(a[:i])%M
    if p not in dict:
        dict[p] = 1
    else:
        ans +=dict[p]
        dict[p] += 1
print(ans)

### FIXED CODE ###

N,M=input().split()
N =int(N)
M =int(M)
a= list(map(int,input().split()))
dict={}
ans = 0
p = 0
dict[0] = 1
for i in range(N):
    p = (p+a[i])%M
    if p not in dict:
        dict[p] = 1
    else:
        ans +=dict[p]
        dict[p] += 1
print(ans)
### BUGGY CODE ###

# coding: utf-8
import math


def calc():
    n = int(input())
    
    tops = list(map(int, input().split()))
    middles = list(map(int, input().split()))
    lowers = list(map(int, input().split()))

    middles = sorted(middles, reverse=True)
    lowers = sorted(lowers, reverse=True)    

    d = {}
    counter = 0
    for top in tops:
        if top in d.keys():
            counter += d[top]
            continue

        c = 0
        for middle in middles:
            if middle <= top:
                break

            for lower in lowers:
                if lower <= middle:
                    break
                
                c += 1
                
        d[top] = c
        counter += c
    
    return counter

count = calc()
print(count)

### FIXED CODE ###

# coding: utf-8
import math
import bisect

def calc():
    n = int(input())
    tops = list(map(int, input().split()))
    middles = list(map(int, input().split()))
    lowers = list(map(int, input().split()))
 
    tops = sorted(tops)
    lowers = sorted(lowers)
 
    counter = 0
 
    for i in range(n):
        # A < B
        top_num = bisect.bisect_left(tops, middles[i])
        
        # B < C
        lower_num = n - bisect.bisect_right(lowers, middles[i])
        
        counter += top_num * lower_num
    
    return counter
 
print(calc())
### BUGGY CODE ###

n = int(input())

l = [int(x) for x in input().split()]
l.sort()
mp = [1]*n

for i in range(n):
    for j in range(i+1,n):
        if(mp[j]==0):
            continue
        if(l[j]==l[i]):
            mp[i] = 0
            mp[j] = 0
            continue
        if(l[j]%l[i]==0):
            mp[j] = 0
            continue

print(sum(mp))

### FIXED CODE ###

n = int(input())
l = [int(x) for x in input().split()]
l.sort()
set_l = set(l)
set_l = sorted(set_l)
limit = 10**6+1
mp = [0]*(limit)
pre = None
for i in range(n):
    num = l[i]
    if(pre==num):
        mp[num] += 1
    pre = num

for x in set_l:
    for y in range(x,limit,x):
        mp[y] += 1
        

cnt = 0
for num in set_l:
    if(mp[num]==1):
        cnt += 1
print(cnt)
### BUGGY CODE ###

import math
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
for i in range(m):
  c=math.floor(max(a)/2)
  a.remove(a[-1])
  a.append(c)
  a.sort()
 
sum=0
for i in range(n):
  sum+=a[i]
  
print(sum)
  

### FIXED CODE ###

from heapq import heapify, heappop, heappush

N, M = map(int, input().split())
A = [-1*int(i) for i in input().split()]
heapify(A)

for i in range(M):
    n = -1 * heappop(A)
    heappush(A, -1*(n//2))

print(-1*sum(A))
### BUGGY CODE ###

M=10**9+7
n,m=map(int,input().split())
F=[1]
for i in range(1,m+1): F+=[i*F[-1]%M]
c=lambda n,r: F[n]*pow(F[r]*F[n-r],-1,M)%M
p=lambda n,r: F[n]*pow(F[n-r],-1,M)%M
a=0
for k in range(n+1):
  a+=(-1)**k*c(n,k)*p(m,k)*p(m-k,n-k)**2%M
print(a%M)

### FIXED CODE ###

M=10**9+7
n,m=map(int,input().split())
F=[1]
for i in range(1,m+1): F+=[i*F[-1]%M]
a=0
for k in range(n+1):
  a+=(-1)**k*F[m-k]*pow(F[k]*F[n-k],-1,M)%M
print(a*F[n]*F[m]*pow(F[m-n]**2,-1,M)%M)
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]*n
for i in range(1,n):
    a = [0]*k
    for j in range(1,k+1):
        if i-j < 0:
            a[j-1] = 10**10
        else:
            a[j-1] = dp[i-j] + abs(h[i]-h[i-j])
    dp[i] = min(a)
print(dp[-1])

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]*n
for i in range(1,n):
    a = [0]*k
    for j in range(1,k+1):
        if i-j < 0:
            a[j-1] = 10**10
        else:
            a[j-1] = dp[i-j] + abs(h[i]-h[i-j])
    dp[i] = min(a)
print(dp[-1])
### BUGGY CODE ###

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

if K == 1:
    print(0)
    exit(0)

minimum = N
previous_value = 1000000000000000001
while True:
    N = abs(N - K)

    if N < minimum:
        minimum = N

    if N >= previous_value:
        break

    previous_value = N

print(minimum)

### FIXED CODE ###

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

if K == 1:
    print(0)
    exit(0)

if N >= K:
    N = N - (N // K) * K

minimum = N
previous_value = 1000000000000000001
while True:
    N = abs(N - K)

    if N < minimum:
        minimum = N

    if N >= previous_value:
        break

    previous_value = N

print(minimum)
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()
count = 0

for i in range(N):
  for j in range(i + 1, N):
    for k in range(j + 1, N):
      if L[k] < L[i] + L[j]:
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()
count = 0
from bisect import bisect_left
for i in range(N - 2):
  for j in range(i + 1, N - 1):    
      count += bisect_left(L, L[i] + L[j]) - 1 - j
      
print(count)
### BUGGY CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
for x in range(N):
  ans = 0
  b = A.pop(x)
  #print(A)
  c = collections.Counter(A)
  #print(c)
  v = [k for j,k in c.items()]
  #print(v)
  for i in v:
    ans += int(i*(i-1)/2)
  print(ans)
  A.insert(x,b)

### FIXED CODE ###

from collections import Counter

n = int(input())
a = [int(x) for x in input().split()]
s = 0
c = Counter(a)
# print(c)
for i in c.values():
    s += i*(i-1)// 2
    
# print(s)
for j in range(n):
    t = c[a[j]]
    print(s-t+1)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
s = [0]
for i in range(n):
    s.append(s[i] + a[i])
t = list(set(s))
def comb(n, r):
    a = 1
    for i in range(n-r+1, n+1):
        a *= i
    for i in range(1, r+1):
        a //= i
    return a

for i in t:
    m = s.count(i)
    ans += comb(m, 2)
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
ans = 0
s = [0]
for i in range(n):
    s.append(s[i] + a[i])

t = Counter(s).most_common()

def comb(n, r):
    a = 1
    for i in range(n-r+1, n+1):
        a *= i
    for i in range(1, r+1):
        a //= i
    return a

for p in t:
    ans += comb(p[1], 2)
print(ans)
### BUGGY CODE ###

A, B, K = map(int, input().split())
center = (A + B) // 2

max_limit = A + K - 1
min_limit = B - K + 1

for i in range(A, center + 1):
    if i <= max_limit:
        print(i)
        
for i in range(center + 1, B + 1):
    if min_limit <= i:
        print(i)

### FIXED CODE ###

A, B, K = map(int, input().split())
center = (A + B) // 2

max_limit = A + K - 1
min_limit = B - K + 1

end_n = center if center <= max_limit else max_limit
for i in range(A, end_n + 1):
    print(i)
        
begin_n = center + 1 if center + 1 >= min_limit else min_limit
for i in range(begin_n, B + 1):
    print(i)
### BUGGY CODE ###

N, M = map(int, input().split())
req = [tuple(map(int, input().split())) for _ in range(M)]
req.sort(key=lambda x: x[1])

res = 0
i = 1
while i <= N:
    remain = [x for x in req if i <= x[0]]
    if len(remain):
        i = remain[0][1]
        res += 1
    else:
        break

print(res)


### FIXED CODE ###

N, M = map(int, input().split())
req = [tuple(map(int, input().split())) for _ in range(M)]
req.sort(key=lambda x: x[1])

res = 0
i = 1
for m in range(M):
    if req[m][0] >= i:
        i = req[m][1]
        res += 1

print(res)
### BUGGY CODE ###

N = int(input())
L = [input() for i in range(N)]
ans = {}
for i in range(len(L)):
    a = L[i]
    b =0
    for i in ans.keys():
        if a ==i:
            b = 1
            ans[i] += 1
            break
        else:
             continue
    if b ==0:
        ans[a] = 1

ans2 = [k for k, v in ans.items() if v == max(ans.values())]
ans2.sort()
[print(i) for i in ans2]


### FIXED CODE ###

N = int(input())
ans = {}
for i in range(N):
    a = input()
    ans[a] = ans.get(a,0) + 1

t = max(ans.values())
ans2 = [k for k, v in ans.items() if v ==t ]
ans2.sort()
[print(i) for i in ans2]
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
input = sys.stdin.buffer.readline

h,w=map(int,input().split())

s=list(input().strip() for _ in range(h))


yoko=[[0]*w for _ in range(h)]
tate=[[0]*w for _ in range(h)]

def yoko_check(y,x,cnt):
    global yoko,s
    if x==w-1:
        yoko[y][x]=cnt
        return cnt
    else:
        if s[y][x+1]==35:
            yoko[y][x]=cnt
            return cnt
        else:
            yoko[y][x]=yoko_check(y,x+1,cnt+1)
            return yoko[y][x]


def tate_check(y,x,cnt):
    global tate,s
    if y==h-1:
        tate[y][x]=cnt
        return cnt
    else:
        if s[y+1][x]==35:
            tate[y][x]=cnt
            return cnt
        else:
            tate[y][x]=tate_check(y+1,x,cnt+1)
            return tate[y][x]


for y in range(h):
    for x in range(w):
        #print(s[y][x])
        if yoko[y][x]==0 and s[y][x]==46:
            yoko_check(y,x,1)
        if tate[y][x]==0 and s[y][x]==46:
            tate_check(y,x,1)

#print(tate)

result=0
for y in range(h):
    for x in range(w):
        if s[y][x]==46:
            result=max(result,tate[y][x]+yoko[y][x]-1)  

print(result)  


### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)

h,w=map(int,input().split())
s=list(input() for _ in range(h))

yoko=[[0]*w for _ in range(h)]
tate=[[0]*w for _ in range(h)]

def yoko_check(y,x,cnt):
    global yoko,s
    if x==w-1:
        yoko[y][x]=cnt
        return cnt
    else:
        if s[y][x+1]=="#":
            yoko[y][x]=cnt
            return cnt
        else:
            yoko[y][x]=yoko_check(y,x+1,cnt+1)
            return yoko[y][x]


def tate_check(y,x,cnt):
    global tate,s
    if y==h-1:
        tate[y][x]=cnt
        return cnt
    else:
        if s[y+1][x]=="#":
            tate[y][x]=cnt
            return cnt
        else:
            tate[y][x]=tate_check(y+1,x,cnt+1)
            return tate[y][x]


for y in range(h):
    for x in range(w):
        if yoko[y][x]==0 and s[y][x]==".":
            yoko_check(y,x,1)
        if tate[y][x]==0 and s[y][x]==".":
            tate_check(y,x,1)

#print(tate)

result=0
for y in range(h):
    for x in range(w):
        if s[y][x]==".":
            result=max(result,tate[y][x]+yoko[y][x]-1)  

print(result)
### BUGGY CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
g = [ list(map(lambda x: int(x)-1, input().split())) for _ in range(M) ]

dp = [ [N+1]*N for _ in range(N)] 

# dp[i][j], i:step, j:path
from collections import Counter, defaultdict
parents = Counter( x[0] for x in g)
childs  = Counter( x[1] for x in g)


parents_dict = defaultdict(lambda :-1)
childs_list  = defaultdict(list)
parents_list  = defaultdict(list)

for x,y in g:
    childs_list[x].append(y)
    parents_dict[y]=x
    parents_list[y].append(x)

# print(parents)
roots = []
for i in range(N):
    # if childs[i] == 0:
    # if len( childs_list[i]) == 0:
    # if parents[i] == 0:
    if childs[i] == 0:
        roots.append(i)

l =  [ (i,childs_list[i], 0) for i in roots]
# l =  [ (i,parents_dict[i], 0) for i in roots]
# print(l)
# exit(0)

costs = [ 0 for _ in range(N)]
ans = 0
while l: 
    # v_idx, pa, cnt = l.pop()
    v_idx, chlist, cnt = l.pop()
    costs[v_idx] = max(costs[v_idx], cnt)
    ans = max(ans, cnt)
    # if parents_dict[pa] != -1:
    for c in chlist:
        if cnt+1 > costs[c]:
            l.append(  (c, childs_list[c], cnt+1) ) 
        # l.append(  (pa, parents_dict[pa], cnt+1) ) 
print(ans)
        
        



### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
g = [ list(map(lambda x: int(x)-1, input().split())) for _ in range(M) ]

from collections import Counter, defaultdict
childs  = Counter( x[1] for x in g)
childs_list  = defaultdict(list)

for x,y in g:
    childs_list[x].append(y)
roots = []
for i in range(N):
    if childs[i] == 0:
        roots.append(i)

l = [ i for i in roots]
costs = [ 0 for _ in range(N)]

while l: 

    nex_stack = []
    # p = l.pop()
    for p in l:
        # cnt = costs[p]
        for c in childs_list[p]:
            costs[c] = max(costs[p]+1, costs[c])
            childs[c] -= 1
            if childs[c] == 0:
                nex_stack.append(c)
    
    l = nex_stack


print(max(costs))
### BUGGY CODE ###

import math
n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7


A_asc = sorted(A)
A_desc = sorted(A, reverse=True)

def nCr(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

MAX = 0
i = 0
r = nCr(n, k)
while r > 0:
    t = nCr(n - 1 - i, k - 1)
    if r > t:
        MAX += (A_desc[i] * t) % mod
        r -= t
    else:
        MAX += (A_desc[i] * r) % mod
        r -= t
    i += 1

MIN = 0
i = 0
r = nCr(n, k)
while r > 0:
    t = nCr(n - 1 - i, k - 1)
    if r > t:
        MIN += (A_asc[i] * t) % mod
        r -= t
    else:
        MIN += (A_asc[i] * r) % mod
        r -= t
    i += 1

print((MAX - MIN + mod) % mod)

### FIXED CODE ###

import math
n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7


def com_init():
    MAX = 10 ** 5 + 1
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * MAX
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv

fac, finv = com_init()

def nCr(n,r):
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod 

# def nCr(n, r):
#     return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


MAX_SUM = 0
MIN_SUM = 0

A.sort() # asc
for j in range(n - k + 1): # 小さい方からk個
    MIN_SUM += A[j] * nCr(n - j - 1, k - 1)

A = A[::-1] # desc
for i in range(n - k + 1): #大きい方からk個
    MAX_SUM += A[i] * nCr(n - i - 1, k - 1)


print((MAX_SUM - MIN_SUM + mod) % mod)
### BUGGY CODE ###

import sys
import math
input = sys.stdin.readline


def main():
    sc = Scan()
    N = sc.intarr()[0]
    S = sc.strarr()[0]

    count = 0

    for i in range(1000):
        # print("--------")
        lucky = format_str(i)
        Flag = 0
        for j in range(N):
            if S[j] == lucky[Flag]:
                Flag += 1
            if Flag == 3:
                count += 1
                break
    print(count)


def format_str(num):
    if num < 10:
        return "00" + str(num)
    elif num < 100:
        return "0" + str(num)
    else:
        return str(num)


class Scan():

    def intarr(self):
        line = input()
        array = line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def intarr_ver(self, n):
        return [int(input()) for _ in range(n)]

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


def display(array):
    for a in range(len(array)):
        if len(array) - a != 1:
            print(array[a], end=' ')
        else:
            print(array[a])


main()


### FIXED CODE ###

import sys
import math
input = sys.stdin.readline


def main():
    sc = Scan()
    _ = sc.intarr()[0]
    S = sc.strarr()[0]

    count = 0

    for i in range(1000):
        # print("--------")
        lucky = format_str(i)
        first = S.find(lucky[0])
        third = S.rfind(lucky[2])

        if first == -1 or third == -1:
            continue
        elif first < third:
            if lucky[1] in S[first + 1:third]:
                count += 1
    print(count)


def format_str(num):
    if num < 10:
        return "00" + str(num)
    elif num < 100:
        return "0" + str(num)
    else:
        return str(num)


class Scan():

    def intarr(self):
        line = input()
        array = line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def intarr_ver(self, n):
        return [int(input()) for _ in range(n)]

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


def display(array):
    for a in range(len(array)):
        if len(array) - a != 1:
            print(array[a], end=' ')
        else:
            print(array[a])


main()
### BUGGY CODE ###

S = input()
K = int(input())
# python のsortは辞書順
substrings = []
for i in range(1, len(S)+1):  # 文字数
    for n in range(len(S) - i + 1):
        sub = S[n:n + i]
        if sub not in substrings:
            substrings.append(sub)
# print(substrings)
substrings.sort()
print(substrings[K-1])


### FIXED CODE ###

# K<=5ということから6文字以上のsubstringには5個以上、辞書順で早いprefixを5個以上もつので
# 長さが5以下の文字列のみをみればいい

S = input()
K = int(input())
substrings = []
for i in range(1, min(len(S)+1, 6)):  # 文字数
    for n in range(len(S) - i + 1):
        sub = S[n:n + i]
        if sub not in substrings:
            substrings.append(sub)
# print(substrings)
substrings.sort()
print(substrings[K-1])
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
for i in range(n):
    cp =x.copy()
    del cp[i]
    print(sorted(cp)[n//2-1])

### FIXED CODE ###

n,*x=map(int, open(0).read().split());xc=sorted(x);
for i in x:print(xc[n//2-(i>(xc[n//2-1]+xc[n//2])/2)])
### BUGGY CODE ###


#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return np.array(x)

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

past = 1
now = 1


for j in range(0,K):
    past = past*A[j]

for i in range(K,N):
    now = past/A[i-K]*A[i]
    if now > past:
        print('Yes')
    else:
        print('No')
    
    past = now
    now = 1






### FIXED CODE ###


#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return np.array(x)

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

for i in range(K,N):
    if A[i] > A[i-K]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

cnt = int(input())
v = []

for i in range(cnt):
    v.append(int(input()))

len = len(v)
dif_max = -1000000000

for i in range(len):
    for j in range(i + 1, len, 1):
        dif = v[j] - v[i]
        dif_max = dif if dif_max < dif else dif_max

print(dif_max)

### FIXED CODE ###

cnt = int(input())
dif_max = -1000000000
v_min = 1000000000

for i in range(cnt):
    buf = int(input())
    if i > 0:
        dif_max = dif_max if buf - v_min < dif_max else buf - v_min
    v_min = buf if buf < v_min else v_min
print(dif_max)
### BUGGY CODE ###

n,k=map(int,input().split())
P=[list(map(int,input().split())) for _ in range(n)]
X=sorted(list(map(lambda x:x[0],P)))
Y=sorted(list(map(lambda x:x[1],P)))
s=(X[0]-X[-1])*(Y[0]-Y[-1])
ans=0
for r in range(n-1,0,-1):
  for l in range(r):
    for u in range(n-1,0,-1):
      for b in range(u):
        c=0
        for p in P:
          if X[l]<=p[0]<=X[r] and Y[b]<=p[1]<=Y[u]:
            c+=1
        if c>=k:
          s=min(s,(X[r]-X[l])*(Y[u]-Y[b]))
        else:break
    if u==n-1 and b==0 and c<k:
      break
print(s)

### FIXED CODE ###

n,k=map(int,input().split())
P=[list(map(int,input().split())) for _ in range(n)]
X=sorted(list(map(lambda x:x[0],P)))
Y=sorted(list(map(lambda x:x[1],P)))
s=(X[0]-X[-1])*(Y[0]-Y[-1])
ans=0
for r in range(n-1,0,-1):
  for l in range(r):
    for u in range(n-1,0,-1):
      for b in range(u):
        c=0
        for p in P:
          if X[l]<=p[0]<=X[r] and Y[b]<=p[1]<=Y[u]:
            c+=1
        if c>=k:
          s=min(s,(X[r]-X[l])*(Y[u]-Y[b]))
        else:break
    if u==n-1 and b==0 and c<k:
      break
print(s)
### BUGGY CODE ###

n=1000000
p=[1]*(n+1)
p[0],p[1]=0,0
for i in range(2,int(n**0.5)+1):
    if p[i]:
        for j in range(i*i,n,i):
            p[j]=0
while 1:
    l=int(input())
    if l==0:break
    ans=-l
    while l:
        l-=1
        a,m=map(int,input().split())
        ans+=sum(p[max(1,a-m)-1:min(n,a+m)])
    print(ans)

### FIXED CODE ###

import bisect
n=1000000
p=[1]*(n+1)
p[0],p[1]=0,0
for i in range(2,int(n**0.5)+1):
    if p[i]:        
        for j in range(i*i,n+1,i):
            p[j]=0
p=[i for i in range(n+1) if p[i]==1]
while 1:
    n=int(input())
    ans=-n
    if n==0:break
    while n:
        n-=1
        a,m=map(int,input().split())
        ans+=bisect.bisect_left(p,a+m+1)-bisect.bisect_left(p,a-m)
    print(ans)
### BUGGY CODE ###

import numpy as np

N, M = map(int, input().split())

keys = [True] * N

l1 = 1
r1 = N

for i in range(M):
    l, r = map(int, input().split())
    if (l1 < l):
        l1 = l
    if (r < r1):
        r1 = r
    newKeys = [False] * N
    for j in range(l1 - 1, r1):
        newKeys[j] = True
    keys = np.logical_and(keys, newKeys)

print(np.sum(keys == True))


### FIXED CODE ###

N, M = map(int, input().split())

keys = [True] * N

l1 = 1
r1 = N

for i in range(M):
    l, r = map(int, input().split())
    if (l1 < l):
        l1 = l
    if (r < r1):
        r1 = r

if (r1 - l1 + 1 > 0):
    print(r1 - l1 + 1)
else:
    print(0)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,A=map(int,input().split())
    x=list(map(lambda x:int(x)-A,input().split()))
    d=defaultdict(int)
    for i in range(2**(N//2)):
        tmp=0
        for j in range(N//2):
            if (i>>j)&1:
                tmp+=x[j]
        d[tmp]+=1
    ans=0
    for i in range(2**(-(-N//2))):
        tmp=0
        for j in range(-(-N//2)):
            if (i>>j)&1:
                tmp+=x[N//2+j]
        ans+=d[-tmp]
    print(ans-1)

if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,A=map(int,input().split())
    x=list(map(int,input().split()))
    dp=[[[0]*2501 for _ in range(N+1)] for _ in range(N+1)]
    dp[0][0][0]=1
    for i in range(N):
        for j in range(i+1):
            for k in range(2501):
                dp[i+1][j][k]+=dp[i][j][k]
                if k-x[i]>=0 and j<=i:
                    dp[i+1][j+1][k]+=dp[i][j][k-x[i]]
    ans=0
    for i in range(1,N+1):
        ans+=dp[-1][i][i*A]
    print(ans)

if __name__ == '__main__':
    main()