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

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  a,b,n=LI()

  # right=n
  # ans=math.floor(a*right/b)-a*math.floor(right/b)
  # left=0
  # while left<=right:
  #   half=(left+right)//2
  #   _ans=math.floor(a*half/b)-a*math.floor(half/b)
  #   if _ans==ans:
  #     return ans
  #   elif _ans>ans:
  #     right=half-1
  #     ans=_ans
  #   else:
  #     left=half+1

  ans=int(a*1/b)-a*int(1/b)
  for i in range(int(math.sqrt(n)),n+1):
    ans=max(ans,int(a*i/b)-a*int(i/b))
  return ans

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  # floor(x/b)がギリギリ割り切れない辺りが一番大きくなりそう
  # -> 実験してみるとmath.floor(a*x/b)-a*math.floor(x/b)はループしてそう
  # -> 答えはfloor(x/b)がギリギリ割り切れないときの値に決め打つぜ！
  a,b,n=LI()
  x=min(n,b-1)
  return math.floor(a*x/b)-a*math.floor(x/b)

# main()
print(main())
### BUGGY CODE ###

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

ans = 10**20
for i in range(N-1):
    p = abs(sum(A[:i+1])-sum(A[i+1:]))
    if ans > p:
        ans = p
print(ans)

### FIXED CODE ###

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

nums = [0]
for a in A:
    nums.append(nums[-1]+a)

sumA = nums[-1]
ans = 10**20
for a in nums[1:-1]:
    p = abs(2*a-sumA)
    ans = min(ans, p)
print(ans)
### BUGGY CODE ###

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

if K >= N:
    print('0')
else:
    H.sort(reverse=True)
    for i in range(K):
        H.pop(0)

    ans = sum(H)
    print(ans)

### FIXED CODE ###

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

if K >= N:
    print('0')
else:
    H.sort(reverse=True)
    H=H[K:]

    ans = sum(H)
    print(ans)
### BUGGY CODE ###

def solve(G,goal):
	cost = 0
	for i in range(n):
		if G[i][goal]:
			cost = max(cost,G[i][goal] + solve(G,i))
	return cost
n,m = map(int,raw_input().split())
G = [[0]*n for i in range(n)]
for i in range(m):
	a,b,c = map(int,raw_input().split())
	G[a][b] = c
print solve(G,n-1)

### FIXED CODE ###

inf = 1e9
n,m = map(int,raw_input().split())
edge = [map(int,raw_input().split()) for i in range(m)]
d = [inf]*n
d[0] = 0
while 1:
	update = 0
	for i in range(m):
		a,b,c = edge[i]
		if d[a] != inf and d[b] > d[a] - c:
			d[b] = d[a] - c
			update = 1
	if update == 0: break
print abs(d[n-1])
### BUGGY CODE ###

from collections import defaultdict, deque
N, M = map(int, input().split())
dic = defaultdict(list)
par =  [0]*(N+1)
dist = [-1]*(N+1)
for i in range(N-1+M):
  a, b = map(int, input().split())
  dic[a] += [b]
  par[b] = a
for i in range(1,N+1):
  if par[i]==0:
    q = deque([(i,0)])
    dist[i] = 0
    break

while q:
  p, cnt = q.popleft()
  if dist[p]>cnt:
    continue
  for e in dic[p]:
    if dist[e]<dist[p]+1:
      dist[e] = dist[p]+1
      q += [(e,dist[e])]
      par[e] = p
for i in range(1,N+1):
  print(par[i])

### FIXED CODE ###

from collections import defaultdict, deque
N, M = map(int, input().split())
dic = defaultdict(list)
par =  [0]*(N+1)
cnt = [0]*(N+1)
for i in range(N-1+M):
  a, b = map(int, input().split())
  dic[a] += [b]
  cnt[b] += 1

for i in range(1,N+1):
  if cnt[i]==0:
    q = deque([i])
    break
  
while q:
  m = q.popleft()
  for c in dic[m]:
    cnt[c] -= 1
    if cnt[c]==0:
      par[c] = m
      q += [c]

for i in range(1,N+1):
  print(par[i])
### BUGGY CODE ###

n=int(input())
arr=[list(input()) for _ in range(n)]
ans=0
for k in range(n):
  flag=True
  for i in range(1,n//2+1):
    for j in range(n):
      if arr[(j)%n][(k+j+i)%n]!=arr[(j+i)%n][(k+j+n)%n]:
        flag=False
        break
    if flag==False:
      break
  else:
    ans+=n
print(ans)

### FIXED CODE ###

n=int(input())
arr=[list(input()) for _ in range(n)]
ans=0
for k in range(n):
  flag=True
  for i in range(1,n//2+1):
    for j in range(n):
      if arr[(j)%n][(k+j+i)%n]!=arr[(j+i)%n][(k+j+n)%n]:
        flag=False
        break
    if flag==False:
      break
  else:
    ans+=n
print(ans)
### BUGGY CODE ###

def gcd(a, b):
    if a % b == 0:
        return b
    return gcd(b, a % b)

k = int(input())
sum_c = 0

for a in range(1, k + 1):
    for b in range(1, k + 1):
        for c in range(1, k + 1):
            p = gcd(a, b)
            sum_c += gcd(c, p)

print(sum_c)

### FIXED CODE ###

from  math import gcd

 
k = int(input())
sum_c = 0
 
for a in range(1, k + 1):
    for b in range(1, k + 1):
        for c in range(1, k + 1):
            sum_c += gcd(gcd(a, b), c)
            
print(sum_c)
### BUGGY CODE ###

import sys

def possible():
    print("POSSIBLE")
    sys.exit()

def main():
    N, M = map(int, input().split())
    hashdict = dict()
    for i in range(7):
        hashdict[i] = list()
    alist = list()
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            temp = b % 7
            hashdict[temp].append(b)
        if b == N:
            alist.append(a)

    for start in alist:
        temp = start % 7
        if start in hashdict[temp]:
            possible()
    print("IMPOSSIBLE")

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def possible():
    print("POSSIBLE")
    sys.exit()

def main():
    N, M = map(int, input().split())
    hashdict = dict()
    for i in range(1009):
        hashdict[i] = list()
    alist = list()
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            temp = b % 1009
            hashdict[temp].append(b)
        if b == N:
            alist.append(a)

    for start in alist:
        temp = start % 1009
        if start in hashdict[temp]:
            possible()
    print("IMPOSSIBLE")

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

import sys
sys.setrecursionlimit(1000000000)

ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

N, M, P = mis()

to = [[] for _ in range(N)]
ot = [[] for _ in range(N)]
edges = []

for i in range(M):
    a,b,c = mis()
    a -= 1
    b -= 1
    c = -(c-P)
    #
    to[a].append(b)
    ot[b].append(a)
    edges.append((a,b,c))

reachableFrom0 = [False] * N
reachableToN = [False] * N

def dfs(n):
    reachableFrom0[0] = True
    nodes = [n]
    while nodes:
        node = nodes.pop()
        for i in to[node]:
            if not reachableFrom0[i]:
                nodes.append(i)
                reachableFrom0[i] = True


def rdfs(n):
    reachableToN[n] = True
    nodes = [n]
    while nodes:
        node = nodes.pop()
        for i in ot[node]:
            if not reachableToN[i]:
                nodes.append(i)
                reachableToN[i] = True

dfs(0)
rdfs(N-1)

ok = [a and b for a, b in zip(reachableFrom0, reachableToN)]

edges = [(a, b, c) for a, b, c in edges if ok[a] and ok[b]]

V = [float('inf')] * N
V[0] = 0

def bf_step():
    for a, b, c in edges:
        V[b] = min(V[b], V[a] + c)

def bf():
    for _ in range(N):
        bf_step()

bf()

Vb = tuple(V)
bf_step()

if tuple(V) == Vb:
    print(max(-V[-1], 0))
else:
    print(-1)




### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

def main():
    N, M, P = mis()
    
    to = [[] for _ in range(N)]
    ot = [[] for _ in range(N)]
    edges = []

    for i in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        c = -(c-P)
        #
        to[a].append(b)
        ot[b].append(a)
        edges.append((a,b,c))

    reachableFrom0 = set()
    reachableToN = set()

    # dfs
    reachableFrom0.add(0)
    nodes = [0]
    while nodes:
        node = nodes.pop()
        for i in to[node]:
            if i not in reachableFrom0:
                nodes.append(i)
                reachableFrom0.add(i)

    #rdfs
    reachableToN.add(N-1)
    nodes = [N-1]
    while nodes:
        node = nodes.pop()
        for i in ot[node]:
            if i not in reachableToN:
                nodes.append(i)
                reachableToN.add(i)


    ok = reachableFrom0 & reachableToN

    edges = tuple((a, b, c) for a, b, c in edges if a in ok and b in ok)

    V = [float('inf')] * N
    V[0] = 0

    def bf(n):
        for _ in range(n):
            upd = False
            for a, b, c in edges:
                if V[b] > V[a] + c:
                    V[b] = V[a] + c
                    upd = True
            if not upd:
                return False
        return True

    bf(N)

    if not bf(1):
        print(max(-V[-1], 0))
    else:
        print(-1)

main()
### BUGGY CODE ###

import sys
file = sys.stdin
H,W = map(int, file.readline().split())
C = [list(map(int,i.split())) for i in file.readlines()]

def height(C):
    P = []
    for i in range(W):
        p = 0
        for j in range(len(C)):
            if C[j][i] == 1:
                p = 0
            else: p += 1
        P.append(p)
    return P

def square(C):
    P = height(C)
    G = []
    L = []
    for i,v in enumerate(P):
        if not L:
            L.append((i, v))
            continue
        if v > L[-1][1]:
            L.append((i, v))
        elif v < L[-1][1]:
            k = i - 1
            while L and v < L[-1][1]:
                a = L.pop()
                G.append((k - a[0] + 1) * a[1])
            L.append((a[0], v))
    while L:
        a = L.pop()
        G.append((len(P) - a[0]) * a[1])
    return max(G)

def ans(C):
    ans = []
    for i in range(H):
        currentC = C[:i+1]
        ans.append(square(currentC))
    return str(max(ans))
print(ans(C))

### FIXED CODE ###

import sys, collections, heapq
file = sys.stdin
H,W = map(int, file.readline().split())
C = [list(map(int,i.split())) for i in file.readlines()]
prev = [0 for i in range(W)]
G = []
def height(C):
    global prev
    P = []
    for i in range(W):
        if C[-1][i] == 1:
            p = 0
        else: p = prev[i] + 1
        P.append(p)
    prev = P[:]
    return P

def square(C):
    P = height(C)
    global G
    L = collections.deque()
    for i,v in enumerate(P):
        if not L:
            L.append((i, v))
            continue
        if v > L[-1][1]:
            L.append((i, v))
        elif v < L[-1][1]:
            k = i - 1
            while L and v < L[-1][1]:
                a = L.pop()
                heapq.heappush(G,  -(k - a[0] + 1) * a[1])
            L.append((a[0], v))
    while L:
        a = L.pop()
        heapq.heappush(G, -(len(P) - a[0]) * a[1])

def ans(C):
    ans = []
    global G
    for i in range(H):
        currentC = C[:i+1]
        square(currentC)
    return str(-G[0])

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

N=int(input())
A=list(map(int,input().split()))
ans=0
AA=[]
M=0
for i in range(N):
    if A[i]<N:
        M=max(A[i],M)

m=min(A)
cnt=0
for i in range(N):
    LM=min(i+M+A[i]+1,N)
    lm=max(i+m+A[i],i+1)
    for j in range(lm,LM):
        cnt+=1
        if j-i==abs(A[i]+A[j]):
            ans+=1
print(ans)

### FIXED CODE ###

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

L={}
R={}
ans=0
for i in range(N):
    if i+A[i] in L:
        L[i+A[i]]+=1
    else:
        L[i+A[i]]=1
    if A[i]<=i:
        if i-A[i] in R:
            R[i-A[i]]+=1
        else:
            R[i-A[i]]=1
for r in R:
    if r in L:
        ans+=L[r]*R[r]
print(ans)
### BUGGY CODE ###

import math

k = int(input())

g =[math.gcd(math.gcd(i+1, j+1), l+1) for i in range(k) for j in range(k) for l in range(k)]
print(sum(g))

### FIXED CODE ###

import math
k = int(input())

sm=0
for i in range(1,k+1):
    for l in range(1,k+1):
        gcdab=math.gcd(i,l)
        for m in range(1,k+1):
            sm+=math.gcd(gcdab,m)

print(sm)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)

def binize(vn):
    res = 0
    for n in vn:
        res |= 1 << (n-1)
    return res


N, M = map(int, input().split())
mK = []
for i in range(M):
    a, b = map(int, input().split())
    vc = list(map(int, input().split()))
    mK.append((a, binize(vc)))

allOpen = 2**N - 1

dA = dict()
dA[0] = [0,]
qA = [0,]

for a, c in mK:
    for aPre in qA:
        for x in dA[aPre]:
            if (x | c) in dA[aPre]:
                continue
            else:
                if (aPre + a) in qA:
                    if allOpen in dA[aPre + a]:
                        continue
                    else:
                        dA[aPre + a].append(x | c) 
                else:
                    dA[aPre + a] = [(x | c),]
                    qA.append(aPre + a)

#print(dA)
#print(max(dA.values()))
#print(allOpen)

res = 10 ** 30
for k in dA:
    if allOpen in dA[k]:
        res = min(res, k)

#print(res)
print(res if res != 10**30 else -1)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

def binize(vn):
    res = 0
    for n in vn:
        res |= 1 << (n-1)
    return res


N, M = map(int, input().split())
mK = []
for i in range(M):
    a, b = map(int, input().split())
    vc = list(map(int, input().split()))
    mK.append((a, binize(vc)))

# 2**N up to 4096
allOpen = 2**N - 1
INF = float("inf")

# dp[i:keyM(<=1000)][n:openedN(<4096)] := min(sum(a))
dp = []
dp.append([0,]+[INF,]*allOpen)

#print(dp)
for na,n in mK:
	nDP = dp[-1]
	for c,pa in enumerate(dp[-1]):
		nDP[n|c] = min(nDP[n|c], pa+na)
	dp.append(nDP)

res = dp[-1][-1]
#print(res)
print(res if res != INF else -1)
### BUGGY CODE ###

S = input()
N = len(S)
# N 文字の文字列 S から、長さ N+1 の ---累積和--- s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

counter = [0] * 2019
indices = []
k = 10
for i in range(N + 1):
    if i == 0:
        sub = 0
    elif i == 1:
        sub = int(S[N - 1])
    else:
        # sub = int(S[N - i] + str(sub))
        sub += int(S[N - i]) * k
        k *= 10
    rest = sub % 2019
    counter[rest] += 1

ans = 0
for r in counter:
    ans += r * (r - 1) // 2
print(ans)

### FIXED CODE ###

S = list(input())
N = len(S)
# N 文字の文字列 S から、長さ N+1 の ---累積和--- s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

counter = [0] * 2019
k = 10
for i in range(N + 1):
    if i == 0:
        sub = 0
    elif i == 1:
        sub = int(S[N - 1])
    else:
        sub += int(S[N - i]) * k
        k *= 10
        k %= 2019
    rest = sub % 2019
    counter[rest] += 1

ans = 0
for r in counter:
    ans += r * (r - 1) // 2
print(ans)
### BUGGY CODE ###

N = int(input())
a = [0]
for _ in range(N):
    a.append(int(input()))
memo = [1]
next = 1
cnt = 0
while True:
    cnt += 1
    next = a[next]
    if next == 2:
        print(cnt)
        break
    if next in memo:
        print(-1)
        break
    memo.append(next)

### FIXED CODE ###

N = int(input())
a = [0]
for _ in range(N):
    a.append(int(input()))
memo = [-1] + [1] + [0] * (N-1)
next = 1
cnt = 0
while True:
    cnt += 1
    next = a[next]
    if next == 2:
        print(cnt)
        break
    if memo[next] == 1:
        print(-1)
        break
    memo[next] = 1
### BUGGY CODE ###

L, R = map(int, input().split())

result = 0

for i in range(L,R+1):
  for j in range(i+1, R+1):
    modResult = (i * j) % 2019 
    if i == L and j == L+1:
      result = modResult
    elif result > modResult:
      result = modResult

print(result)

### FIXED CODE ###

L, R = map(int, input().split())
counter = 0
result = 0

for i in range(L,R+1):
  counterJ = 0
  for j in range(i+1, R+1):
    modResult = (i * j) % 2019 
    if i == L and j == L+1:
      result = modResult
    elif result > modResult:
      result = modResult
    if counterJ == 2019:
      break
    counterJ += 1
    
  counter += 1
  if counter == 2019:
    break;
    
print(result)
### BUGGY CODE ###

import time

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

INF = 10 ** 20


dp = [INF for i in range(h + 10**4)]
dp[0] = 0

magic = []

for i in range(n):
    magic.append(list(map(int, input().split())))


que = [0]
cc = [0]
m = 0
c = 0
for i in range(h):
    if dp[i] == INF:
        continue
    for a, b in magic:
        dam = i + a
        if dp[dam] > dp[i] + b:
            dp[dam] = dp[i] + b

ans = min(dp[h:])

print(ans)

### FIXED CODE ###

def main():
    inf = 10**9
    H, N = map(int, input().split())
    AB = []
    for n in range(N):
        a, b = map(int, input().split())
        AB.append((a, b))
    AB.sort(reverse=True, key=lambda x: x[0])
    dp = [inf] * (H + 10 ** 4)
    dp[0] = 0
    for a, b in AB:
        for h in range(H):
            if dp[h] != inf:
                tmp = dp[h] + b
                if tmp < dp[h + a]:
                    dp[h + a] = tmp
    print(min(dp[H:]))
 
 
main()
### BUGGY CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n = ni()
a = [ni() for _ in range(n)]

a.sort()
b = 0
count = 0
ans = 0
for i in a:
    if b != i:
        count = a.count(i)
        if count % 2 != 0:
            ans += 1
        else:
            pass
    else:
        pass
    b = i

print(ans)


### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n = ni()
s = set()
for i in range(n):
    x = ni()
    if x in s:
        s.remove(x)
    else:
        s.add(x)
print(len(s))
### BUGGY CODE ###

from collections import deque

def main():
    n = input()
    A = map(int,raw_input().split())
    q = input()
    M = map(int,raw_input().split())

    W = map(lambda m:sub(m,n,A), M)
    for w in W:
        print w
        
def sub(m,n,A):
    qA = deque(A)
    for j in range(n):
        w = rec(m,qA)
        if w:
            break
        qA.popleft()            
    if w:
        return "yes"
    else:
        return "no"
    
def rec(m,A):
    Ac = deque(list(A)[:])
    Ad = deque(list(A)[:])
    m_new = m
    if m_new == 0:
        r1 = True
    elif m_new < 0:
        r1 = False
    else:
        if len(A) == 1:
            r1 = False
        else:
            Ac.popleft()
            r1 = rec(m_new,Ac)
    m_new = m - Ad[0]
    if m_new == 0:
        r2 = True
    elif m_new < 0:
        r2 = False
    else:
        if len(A) == 1:
            r2 = False
        else:
            Ad.popleft()
            r2 = rec(m_new,Ad)
    if r1 or r2:
        return True
    else:
        return False

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque

def main():
    n = input()
    A = deque(map(int,raw_input().split()))
    q = input()
    M = map(int,raw_input().split())

    p = rec([0],A)

    for m in M:
        if m in p:
            print "yes"
        else:
            print "no"

def rec(a,A):
    if len(A) == 0:
        return a
    else:
        y = A.popleft()
        a = a+[x+y for x in a]
        return rec(a,A)

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

r1,c1,r2,c2 = map(int,input().split())
mod = 10**9+7
fact = [1]*(3*10**6)

for n in range(3*10**6-1):
    fact[n+1] = ((n+1)*fact[n])%mod

def comb(n,k):
    return (fact[n]*pow(fact[k],mod-2,mod)*pow(fact[n-k],mod-2,mod))%mod

def fs(r,c):
    res = 0
    for i in range(1,c+1):
        res += comb(i+1+r,r)-1
    return res

ans = fs(r2,c2)-fs(r1-1,c2)-fs(r2,c1-1)+fs(r1-1,c1-1)
ans %= mod
print(ans)

### FIXED CODE ###

r1,c1,r2,c2 = map(int,input().split())
mod = 10**9+7
fact = [1]*(2*10**6+11)

for n in range(2*10**6+10):
    fact[n+1] = ((n+1)*fact[n])%mod

factinv = [1]*(2*10**6+10)
for n in range(10**6+10):
    factinv[n] = pow(fact[n],mod-2,mod)

def comb(n,k):
    return (fact[n]*factinv[n-k]*factinv[k])%mod

def fs(r,c):
    res = 0
    for i in range(1,c+1):
        res += comb(i+1+r,r)-1
    return res

ans = fs(r2,c2)-fs(r1-1,c2)-fs(r2,c1-1)+fs(r1-1,c1-1)
ans %= mod
print(ans)
### BUGGY CODE ###

N = int(input())
L = sorted([int(x) for x in input().split()],reverse=True)
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        if L[j] < L[i] / 2:
            break
        for k in range(j+1, N):
            if L[i] < L[j] + L[k]:
                ans += 1
            else:
                break
print(ans)

### FIXED CODE ###

import bisect

N = int(input())
L = sorted([int(x) for x in input().split()])
ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        ab = L[i] + L[j]
        r = bisect.bisect_left(L,ab)
        l = j + 1
        ans += r - l

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

n,a=map(int,input().split())
x=list(map(int,input().split()))
dp=[[[0 for i in range(2501)] for j in range(n+1)] for k in range(n+1)]
#dp[i][j][k]:=i枚目まで見てj枚選んで和がkとなるようなカードの取り方の数
dp[0][0][0]=1
for i in range(n):
    see=x[i]
    for j in range(i+2):
        for k in range(2501):
            dp[i+1][j][k]+=dp[i][j][k]
            if see>k or j==0:continue
            dp[i+1][j][k]+=dp[i][j-1][k-see]
ans=0
for i in range(1,n+1):
    ans+=dp[-1][i][i*a]
print(ans)

### FIXED CODE ###

n,a=map(int,input().split())
x=list(map(int,input().split()))
dp=[[[0 for i in range(2501)] for j in range(k+2)] for k in range(n+1)]
#dp[i][j][k]:=i枚目まで見てj枚選んで和がkとなるようなカードの取り方の数
dp[0][0][0]=1
for i in range(n):
    see=x[i]
    for j in range(i+2):
        for k in range(2501):
            dp[i+1][j][k]+=dp[i][j][k]
            if see>k or j==0:continue
            dp[i+1][j][k]+=dp[i][j-1][k-see]
ans=0
for i in range(1,n+1):
    ans+=dp[-1][i][i*a]
print(ans)