Problem:
 Score : 300 points    Problem Statement Tak has N cards. On the i -th (1 \leq i \leq N) card is written an integer x_i .
He is selecting one or more cards from these N cards, so that the average of the integers written on the selected cards is exactly A .
In how many ways can he make his selection?      Constraints  1 \leq N \leq 50  1 \leq A \leq 50  1 \leq x_i \leq 50  N,\,A,\,x_i are integers.       Partial Score  200 points will be awarded for passing the test set satisfying 1 \leq N \leq 16 .         Input The input is given from Standard Input in the following format:  N  A  x_1  x_2  ...  x_N       Output Print the number of ways to select cards such that the average of the written integers is exactly A .        Sample Input 1 4 8
7 9 8 9      Sample Output 1 5   The following are the 5 ways to select cards such that the average is 8 :  Select the 3 -rd card.  Select the 1 -st and 2 -nd cards.  Select the 1 -st and 4 -th cards.  Select the 1 -st, 2 -nd and 3 -rd cards.  Select the 1 -st, 3 -rd and 4 -th cards.          Sample Input 2 3 8
6 6 9      Sample Output 2 0       Sample Input 3 8 5
3 6 2 8 7 6 5 9      Sample Output 3 19       Sample Input 4 33 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3      Sample Output 4 8589934591   The answer may not fit into a 32 -bit integer.

Solution (Python):
import sys
input = sys.stdin.readline

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

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

for i in range(1, N + 1):
    for j in range(-2500, 2501):
        if 5000 >= j + 2500 - x[i - 1] >= 0:
            dp[i][j + 2500] = dp[i - 1][j + 2500 - x[i - 1]] + dp[i - 1][j + 2500]
        else:
            dp[i][j + 2500] = dp[i - 1][j + 2500]

print(dp[N][0 + 2500] - 1)

Solution (Python):
N,A = map(int,input().split())
X = list(map(int,input().split()))

Xp = [0]
Xm = [0]
Xz = 0
for x in X:
    if x-A > 0:
        Xp.append(x-A)
    elif x-A < 0:
        Xm.append(x-A)
    else:
        Xz += 1

DPp = [[0 for j in range(2501)] for i in range(len(Xp))]
DPm = [[0 for j in range(2501)] for i in range(len(Xm))]

DPp[0][0] = 1
DPm[0][0] = 1

for i in range(1,len(DPp)):
    x = Xp[i]
    for j in range(2501):
        if j >= x:
            DPp[i][j] = DPp[i-1][j] + DPp[i-1][j-x]
        else:
            DPp[i][j] = DPp[i-1][j]

for i in range(1,len(DPm)):
    x = -Xm[i]
    for j in range(2501):
        if j >= x:
            DPm[i][j] = DPm[i-1][j] + DPm[i-1][j-x]
        else:
            DPm[i][j] = DPm[i-1][j]

ans = 1

for j in range(1,2501):
    ans += DPp[len(DPp)-1][j]*DPm[len(DPm)-1][j]
ans = ans*pow(2,Xz) - 1
print(ans)

Solution (Python):
N,A = map(int,input().split())
X = list(map(int,input().split()))

Xp = [0]
Xm = [0]
Xz = 0
for x in X:
    if x-A > 0:
        Xp.append(x-A)
    elif x-A < 0:
        Xm.append(x-A)
    else:
        Xz += 1

DPp = [[0 for j in range(2501)] for i in range(len(Xp))]
DPm = [[0 for j in range(2501)] for i in range(len(Xm))]

DPp[0][0] = 1
DPm[0][0] = 1

for i in range(1,len(DPp)):
    x = Xp[i]
    for j in range(2501):
        if j >= x:
            DPp[i][j] = DPp[i-1][j] + DPp[i-1][j-x]
        else:
            DPp[i][j] = DPp[i-1][j]

for i in range(1,len(DPm)):
    x = -Xm[i]
    for j in range(2501):
        if j >= x:
            DPm[i][j] = DPm[i-1][j] + DPm[i-1][j-x]
        else:
            DPm[i][j] = DPm[i-1][j]

ans = 1

for j in range(1,2501):
    ans += DPp[len(DPp)-1][j]*DPm[len(DPm)-1][j]
ans = ans*pow(2,Xz) - 1
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def array(*args, initial=0):
    pre = "["*len(args)
    post = ""
    for a in args[::-1]:
        post += " for _ in range("+str(a)+")]"
    S = pre + str(initial) + post
    return eval(S)


def solve(N: int, A: int, x: "List[int]"):
    M = sum(x)
    
    DP = array(N+1, N+1, M+1)
    DP[0][0][0] = 1

    for i, a in enumerate(x, start=1):
        for j in range(N+1):
            for tot in range(M+1):
                DP[i][j][tot] = DP[i-1][j][tot]  
                if tot - a >= 0:                 
                    DP[i][j][tot] += DP[i-1][j-1][tot-a]

    ans = 0
    for j in range(1, N+1):
        for tot in range(M+1):
            if tot / j == A:
                
                ans += DP[-1][j][tot]
    print(ans)
    
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = int(next(tokens))  
    x = [int(next(tokens)) for _ in range(N)]  
    solve(N, A, x)


if __name__ == '__main__':
    main()

Solution (Python):
n, a = map(int, input().split())
x = list(map(int, input().split()))

dp = [[[0] * 3000 for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1

for i in range(n):
    for j in range(n):
        for k in range(2500):
            dp[i + 1][j + 1][k + x[i]] += dp[i][j][k]
            dp[i + 1][j][k] += dp[i][j][k]

ans = 0
for i in range(1, n + 1):
    ans += dp[n][i][i * a]

print(ans)

Solution (Python):
N, A = map(int, input().split())
x = list(map(int, input().split()))
MAX_J = sum(x)
dp = [[0] * (MAX_J+1) for i in range(N+1)]
dp[0][0] = 1
for n in range(N):
    for i in range(N)[::-1]:
        for j in range(MAX_J-x[n]+1)[::-1]:
            dp[i+1][j+x[n]] += dp[i][j]
ans = 0
for i in range(1, N+1):
    if A * i <= MAX_J:
        ans += dp[i][A * i]
print(ans)

Solution (Python):
N, A = map(int, input().split())
X = list(map(int, input().split()))
dp = [[[0] * 3001 for i in range(51)] for j in range(51)]

dp[0][0][0] = 1

for i in range(N):
  for j in range(N):
    for k in range(0, 2501):
      dp[i+1][j][k] += dp[i][j][k]
      dp[i+1][j+1][k+X[i]] += dp[i][j][k]

ans = 0
for n in range(1, N+1):
  ans += dp[N][n][n*A]

print(ans)

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]


def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,a = get_nums_l()
xxx = get_nums_l()

valMax = 2505


dp = [ [ [0]*valMax for __ in range(n+1) ] for _ in range(n+1) ]

for j in range(n+1):
    for k in range(valMax):
        dp[n][j][k] = 1 if k == j*a else 0

for i in range(n-1, -1, -1):
    for j in range(i+1):
        for k in range(valMax):
            no_pic = dp[i+1][j][k]
            pic = dp[i+1][j+1][k + xxx[i]] if k+xxx[i] < valMax else 0
            dp[i][j][k] = no_pic + pic
            
                

print(dp[0][0][0] - 1)

Solution (Python):

import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, A: int, x: "List[int]"):
    dp = [[0] * (A * N + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for xi in x:
        for k in reversed(range(1, N + 1)):
            for j in range(xi, A * N + 1):
                if j >= xi:
                    dp[k][j] += dp[k - 1][j - xi]
    print(sum(dp[i][A * i] for i in range(1, N + 1)))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = int(next(tokens))  
    x = [int(next(tokens)) for _ in range(N)]  
    solve(N, A, x)


if __name__ == '__main__':
    main()

Solution (Python):
N,A = map(int,input().split())
X = list(map(int,input().split()))
ans = 0

def make_array(dims,fill):
    if len(dims) == 1:
        return [fill]*dims[0]
    ret = []
    nxt = dims[1:]
    for i in range(dims[0]):
        ret.append(make_array(nxt,fill))
    return ret
S = sum(X)+1
dp = make_array([N+2,N+2,S],0)
dp[0][0][0] = 1
for i in range(N):
    for j in range(N):
        for s in range(S-X[i]):
            dp[i+1][j+1][s+X[i]] += dp[i][j][s]
            dp[i+1][j][s] += dp[i][j][s]
ans = 0
for j in range(1,N+1):
    for s in range(1,S+1):
        if j*A == s:
            ans += dp[-2][j][s]
print(ans)

Solution (Python):
n,a = map(int,input().split())
xx = list(map(int,input().split()))

sm = sum(xx)
dp = [[0 for j in range(sm+1)] for i in range(n+1)]
dp[0][0] = 1
for x in xx:
    for i in range(1,n+1)[::-1]:
        for j in range(x,sm+1)[::-1]:
            
            dp[i][j] += dp[i-1][j-x]

ans = 0
for i in range(1, min(sm // a,n) + 1):
    ans += dp[i][i*a]
print(ans)

Solution (Python):
n, a = map(int, input().split())
x_i = map(int, input().split())
list = list(i - a for i in x_i)
anslist = [[0 for i in range(5001)] for j in range(n + 1)]
anslist[0][2500] += 1
anslist[1][2500] += 1
anslist[1][list[0] + 2500] += 1
for id in range(n + 1):
    if id == 0 or id == 1: continue
    num = list[id - 1]
    for x in range(5001):
        anslist[id][x] += anslist[id - 1][x]
        if 0 <= x - num < 5001:
            anslist[id][x] += anslist[id - 1][x - num]
print(anslist[n][2500] - 1)

Solution (Python):
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(2451):
            dp[i + 1][j][k] += dp[i][j][k]
            dp[i + 1][j + 1][k + x[i]] += dp[i][j][k]

ans = 0
for j in range(1, n + 1):
    ans += dp[n][j][j * a]

print(ans)

Solution (Python):
N,A=map(int,input().split())
x=list(map(int,input().split()))
ans=0
y=[0]*(len(x))
for k in range(len(x)):
    y[k]=x[k]-A
minus=0
plus=0
for k in range(N):
    if y[k]<0:
        minus-=y[k]
    if y[k]>0:
        plus+=y[k]
total=minus+plus+1
ans=[[0 for i in range(N)]for j in range(total)]
ans[y[0]+minus][0]=1
ans[minus][0]=ans[minus][0]+1
for j in range(N-1):
    for t in range(total):
        if 0<=t-y[j+1]<total:
            ans[t][j+1] =ans[t][j]+ans[t-y[j+1]][j]
        else:
            ans[t][j+1] =ans[t][j]
print(ans[minus][N-1]-1)

Solution (Python):

n,a=map(int,input().split())
x=list(map(int,input().split()))

max_num=max(n*a,sum(x))
dp=[[[0]*(max_num+1) for j in range(n+1)] for i in range(n+1)]
dp[0][0][0]=1
for i in range(n):
    for j in range(n):
        for k in range(max_num):
            if dp[i][j][k]:
                
                dp[i+1][j][k] += dp[i][j][k]
                
                dp[i+1][j+1][k+x[i]] += dp[i][j][k]

ans=0
for i in range(1,n+1):
    ans+=dp[n][i][i*a]
print(ans)

Solution (Python):
import numpy as np
N, A = map(int, input().split())
X = [int(c) for c in input().split()]
dp = np.zeros((51,51,2501))
dp[:,0,0] = 1
for i in range(1,N+1):
  c = X[i-1]
  for k in range(1,N+1):
    dp[i,k,:c] = dp[i-1,k,:c]
    dp[i,k,c:] = dp[i-1,k,c:]+dp[i-1,k-1,:2501-c]
ans = 0
for i in range(1,N+1):
  ans += dp[N,i,i*A]
print(int(ans))

Solution (Python):
from functools import lru_cache

N, A = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(lambda i: i - A, x))
X = max(max(x), A)

@lru_cache(maxsize=None)
def solve(j, t):
    global y
    if j == 0 and t == 0:
        return 1
    elif j >= 1 and (t < y[j - 1] - N * X or t > y[j - 1] + N * X):
        return solve(j - 1, t)
    elif j >= 1 and t >= y[j - 1] - N * X and t <= y[j - 1] + N * X:
        return solve(j - 1, t) + solve(j - 1, t - y[j - 1])
    else:
        return 0

print(solve(N, 0) - 1)

Solution (Python):

import sys

def solve(N: int, A: int, x: "List[int]"):
    
    dp = [[[0]*2501 for _ in range(N+1)] for _ in range(N+1)]

    for i in range(N):
        dp[i][0][0] = 1

    for i in range(N):
        for j in range(N):
            for k in range(2501):
                if k-x[i] >= 0:
                    dp[i+1][j+1][k] = dp[i][j][k-x[i]]+dp[i][j+1][k]
                else:
                    dp[i+1][j+1][k] = dp[i][j+1][k]

    answer = 0
    for j in range(1,N+1):
        answer += dp[N][j][A*j]
    print(answer)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = int(next(tokens))  
    x = [int(next(tokens)) for _ in range(N)]  
    solve(N, A, x)

if __name__ == '__main__':
    main()

Solution (Python):
from functools import lru_cache
N, A = map(int, input().split())
X = [int(x) for x in input().split()]



assert len(X) == N
def solve0(i, n, s):
    if s < 0:
        return -1
    if N-i+1 < n:
        return -1
    if n == 0:
        if s == 0:
            return 1
        else:
            return -1
    if i == N:
        return -1
    s1 = solve(i+1, n-1,s-X[i])
    s2 = solve(i+1, n, s)
    if s1 == -1 and s2 == -1:
        return -1
    if s1 == -1:
        return s2
    if s2 == -1:
        return s1
    return s1 + s2

cache = {}
def solve(i, n, s):
    key = (i, n, s)
    a = cache.get(key, None)
    if a is None:
        a = solve0(i, n, s)
        cache[key] = a
    return a

answer = 0
for n in range(1, N+1):
    s = solve(0, n, n*A)
    if s != -1:
        answer += s
print(answer)

Solution (Python):
N, A = map(int, input().split())
X = list(map(int, input().split()))
dp = [[0]*2501 for _ in range(N+1)] 
dp[0][0] = 1

for i, x in enumerate(X):
  for n in range(i+1, 0, -1):
    for k in range(x, 2501):
      dp[n][k] += dp[n-1][k-x]

ans = 0
for n in range(1, N+1):
  ans += dp[n][A*n]
print(ans)

Solution (Python):
N, A = map(int, input().split())
X = list(map(int, input().split()))


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


for i in range(N) :
    for j in range(N) :
        for k in range(N*50):
            
            dp[i + 1][j][k] += dp[i][j][k]
            
            
            dp[i + 1][j + 1][k + X[i]] += dp[i][j][k]

ans = 0
for i in range(1, N+1):
    ans += dp[N][i][i*A]
    
print(ans)

Solution (Python):
N,A=map(int, input().split())
x=tuple(map(lambda i:int(i)-A,input().split()))
l=[0]*5001
l[0]=1
for i in x:
    f=l.copy()
    for j in range(-2500,2501):
        if l[j]:
            f[i+j]+=l[j]
    l=f.copy()
print(l[0]-1)

Solution (Python):
import sys
from functools import lru_cache

input = sys.stdin.readline


ans = 0
X = []
A = 0

@lru_cache(maxsize=None)
def solve(i, selected, total):
    global X, ans

    if i == len(X):
        if selected != 0 and total == (selected * A):
            return 1
        return 0

    ret = 0
    ret += solve(i + 1, selected + 1, total + X[i])
    ret += solve(i + 1, selected, total)
    return ret


def main():
    global X, ans, A
    N, A = [int(x) for x in input().split()]
    X = [int(x) for x in input().split()]

    print(solve(0, 0, 0))

    
if __name__ == '__main__':
    main()

Solution (Python):
import sys
from functools import lru_cache

input = sys.stdin.readline


ans = 0
X = []
A = 0

@lru_cache(maxsize=None)
def solve(i, selected, total):
    global X, ans

    if i == len(X):
        if selected != 0 and total == (selected * A):
            return 1
        return 0

    ret = 0
    ret += solve(i + 1, selected + 1, total + X[i])
    ret += solve(i + 1, selected, total)
    return ret


def main():
    global X, ans, A
    N, A = [int(x) for x in input().split()]
    X = [int(x) for x in input().split()]

    print(solve(0, 0, 0))

    
if __name__ == '__main__':
    main()

Solution (Python):


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

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

dp=[[0]*2501 for i in range(50)]

for x in X:
    for i in range(49)[::-1]:
        for index,item in enumerate(dp[i]):
            if item!=0:
                dp[i+1][index+x]+=dp[i][index]
    dp[0][x]+=1

ans=0
for i in range(50):
    ans+=dp[i][A*(i+1)]

print(ans)

Solution (Python):
N, A = map(int, input().split())
X = list(map(int, input().split()))
S = max(N * A, sum(X))
DP = [[[0] * (S+1) for _ in range(N+1)] for _ in range(N+1)]
DP[0][0][0] = 1
for i in range(N):
    for j in range(N+1):
        for k in range(S+1):
            if not DP[i][j][k]: continue
            DP[i+1][j][k] += DP[i][j][k]
            if j != N:
                DP[i+1][j+1][k+X[i]] += DP[i][j][k]
print(sum(DP[N][j][j*A] for j in range(1, N+1) if j * A <= S))

Solution (Python):
n, a = map(int, input().split())
x = list(map(int, input().split()))

max_s = sum(x)
dp = [[[0 for i in range(max_s + 1)] for j in range(n+1)] for k in range(len(x) + 1)]

dp[0][0][0] = 1
dp[1][0][0] = 1
for i in range(1,n+1):
    num = x[i-1]
    for j in range(len(x)+1):
        for k in range(max_s + 1):
            if k - num < 0:
                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-num]
ans = 0
for i in range(len(x)+1):
    if i * a <= max_s+1:
        ans += dp[-1][i][i*a]
print(ans-1)

Solution (Python):
N, A = map(int, input().split())
x = list(map(int, input().split()))
for i in range(N):
    x[i] -= A
max_x = max(max(x), A)

dp = [[0]*(2*N*max_x + 1) for i in range(N+1)]
dp[0][N*max_x] = 1

for i in range(N):
    for k in range(2*N*max_x + 1):
        dp[i+1][k] = dp[i][k]
        if 0 <= k - x[i] and k - x[i] <= 2*N*max_x:
            dp[i+1][k] += dp[i][k - x[i]]

print(dp[N][N*max_x] - 1)

Solution (Python):
import numpy as np

n,a = map(int, input().split())
X = np.array(input().split(), dtype=np.int64)
Y = X-a
U = max(X.max(), a) * n
dp = np.zeros(2*U+1, dtype=np.int64)
dp[U] = 1
for i in range(n):
  y = Y[i]
  if y >= 0:
    dp[y:] = dp[y:] + dp[:2*U+1-y]
  else:
    dp[:y] = dp[:y] + dp[-y:]
print(dp[U]-1)

Solution (Python):
n,a=map(int,input().split())
x=list(map(int,input().split()))
x.sort(reverse=True)
sx=sum(x)
dp=[[0]*(n+1) for i in range(sx+1)]
dp[0][0]=1
for i in range(n):
    dp_sub=[[0]*(n+1) for j in range(sx+1)]
    for j in range(sx+1):
        for k in range(n+1):
            if (j==0 and k==0) or dp[j][k]!=0:
                dp_sub[j+x[i]][k+1]=dp[j][k]
    for j in range(sx+1):
        for k in range(n+1):
            dp[j][k]+=dp_sub[j][k]
cnt=0

for i in range(min(sx//a,n)):
    cnt+=dp[a*(i+1)][i+1]

print(cnt)

Solution (Python):
from collections import defaultdict

n, a = map(int, input().split())
arr = [x-a for x in list(map(int, input().split()))]

dct = defaultdict(int)
dct[0] = 1

for x in arr:
    for k, v in list(dct.items()):
        dct[k+x] += v

print(dct[0]-1)

Solution (Python):
N, A = map(int, input().split())
X = list(map(int, input().split()))
for i in range(N):
  X[i] -= A
D = {0: 1}
for i in X:
  S = [[j, D[j]] for j in D]
  for j in S:
    if j[0] + i in D:
      D[j[0]+i] += j[1]
    else:
      D[j[0]+i] = j[1]
print(D[0]-1)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

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

dp = [[[0 for _ in range(51)] for __ in range(2501)] for ___ in range(51)]

def main():
    N, A = LI()
    X = LI()
    dp[0][0][0] = 1
    
    

    for i in range(N):
        for j in range(2501):
            for k in range(N+1):
                if j - X[i] >= 0 and k - 1 >= 0:
                    dp[i+1][j][k] += dp[i][j-X[i]][k-1]
                dp[i+1][j][k] += dp[i][j][k]
    cnt = 0
    for k in range(1, N+1):
        cnt += dp[N][k*A][k]
    print(cnt)
main()

Solution (Python):
N, A=map(int, input().split())
x=list(map(int, input().split()))

dp=[[[0]*2501 for j in range(N+1)] for i in range(N)]

dp[0][0][0]=1
dp[0][1][x[0]]=1
for i in range(1, N):
  dp[i][0][0]=1
  for j in range(1, i+2):
    for k in range(2501):
      if k-x[i]>=0:
        dp[i][j][k]=dp[i-1][j-1][k-x[i]]+dp[i-1][j][k]
      else:
        dp[i][j][k]=dp[i-1][j][k]
        
print(sum([dp[-1][j][A*j] for j in range(1, N+1)]))

Solution (Python):
MAX_INDEX = 51
MAX_SUM = 2505

dp = [[[-1 for _ in range(MAX_INDEX)] for _ in range(MAX_SUM)] for _ in range(MAX_INDEX)]

def waysutil(index, sum, count, arr, K) : 

	if (index < 0) : 
		return 0; 

	if (index == 0) : 

		if (count == 0) : 
			return 0; 
			
		remainder = sum % count; 

		if (remainder != 0) : 
			return 0; 
			
		average = sum // count; 

		if (average == K) : 
			return 1; 

	if (dp[index][sum][count] != -1) : 
		return dp[index][sum][count]; 

	dontpick = waysutil(index - 1, sum, count, arr, K); 


	pick = waysutil(index - 1, sum + arr[index], count + 1, arr, K); 
						
	total = pick + dontpick; 

	dp[index][sum][count] = total; 
	
	return total; 


def ways(N, K, arr) : 

	Arr = []; 

	Arr.append(-1); 
	for i in range(N) : 
		Arr.append(arr[i]); 

	answer = waysutil(N, 0, 0, Arr, K); 
	return answer; 


n, k = map(int, input().split())
arr = list(map(int, input().split()))
N = len(arr)

print("%d" % (ways(N, k, arr)))

Solution (Python):

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




max_wa = max(X) * N
dp = [[[0] * (max(X) * (N+1)) for _ in range(N+1)] for __ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for k in range(i+1):
        for wa in range(max_wa):
            
            dp[i+1][k+1][wa+X[i]] += dp[i][k][wa]
            
            dp[i+1][k][wa] += dp[i][k][wa]

ans = 0
for k in range(1, N+1):
    if k * A > max_wa:
        break
    ans += dp[-1][k][k*A]

print(ans)

Solution (Python):
n,a=map(int,input().split())
x=list(map(int,input().split()))
for i in range(len(x)):
    x[i]-=a
li=[[0]*5001 for i in range(n+1)]
for i in range(n):
    li[i+1][2500+x[i]]+=1
    for j in range(5001):
        if li[i][j]>=1:
            li[i+1][j+x[i]]+=li[i][j]
            li[i+1][j]+=li[i][j]
    
print(li[n][2500])

Solution (Python):
import numpy as np


n, a = map(int, input().split())
X = np.array(list(map(int, input().split())))
X -= a

plus = X[X > 0]
zero = X[X == 0]
minus = abs(X[X < 0])

num_count = np.zeros(2551, dtype=np.int64)
num_count[0] = 1

for num in plus:
    num_count[num:] = num_count[:-num] + num_count[num:]

for num in minus:
    num_count[:-num] = num_count[:-num] + num_count[num:]

ans = 2 ** len(zero) * (num_count[0])

print(ans-1)

Solution (Python):

N, A = map(int, input().split(' '))
import collections

X = [int(a) - A for a in input().split(' ')]
sum_positives = sum([x for x in X if x > 0])
sum_negatives = sum([x for x in X if x < 0])

dp = [dict([(i, 0) for i in range(sum_negatives, sum_positives+1)])
            for _ in range(N+1)]
dp[0][0] = 1

for i, x in enumerate(X):
    for j in range(sum_negatives, sum_positives+1):
        dp[i + 1][j] = dp[i][j]
        if (j - x) in dp[i]:
            dp[i + 1][j] += dp[i][j - x]




print(dp[N][0] - 1)
exit()

Solution (Python):
N,A = map(int,input().split())
X = list(map(int,input().split()))
for i in range(N):
    X[i] -= A
dp = [[0 for i in range(5001)] for i in range(N+1)]
dp[0][2500] = 1
u = 2500
d = 2500
for i in range(1,N+1):
    x = X[i-1]
    if x <= 0:
        d += x
    else:
        u += x
    for j in range(d,u+1):
        dp[i][j] += dp[i-1][j-x] + dp[i-1][j]
print(dp[N][2500]-1)

Solution (Python):


import sys
from collections import defaultdict

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()

A = [a-K for a in LIST()]


dp = [defaultdict(int) for i in range(N+1)]
dp[0][0] = 1
for i, a in enumerate(A):
    for k, v in dp[i].items():
        dp[i+1][k] += v
        dp[i+1][k+a] += v

print(dp[N][0] - 1)

Solution (Python):
n, a = map(int, input().split())
X = list(map(int, input().split()))



sum_X = sum(X)
DP = [[[0 for _ in range(sum_X+1)] for _ in range(n+1)] for _ in range(n+1)]


for j in range(n+1):
    for k in range(n+1):
        for s in range(sum_X+1):
            if (j==0) and (k==0) and (s==0):
                DP[j][k][s] = 1
            elif (j >= 1) and (s < X[j-1]):
                DP[j][k][s] = DP[j-1][k][s]
            elif (j >= 1) and (k >= 1) and (s >= X[j-1]):
                DP[j][k][s] = DP[j-1][k][s] + DP[j-1][k-1][s-X[j-1]]
            else:
                DP[j][k][s] = 0

ans  = 0
for k in range(1, n+1):
    if a*k > sum_X:
        pass
    else:
        ans += DP[n][k][a*k]

print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def main():
    N,A = map(int,input().split())
    x = list(map(int,input().split()))
    S = sum(x)
    
    dp = [[[0 for _ in range(S+1)] for _ in range(N+1)] for _ in range(N+1)]
    dp[0][0][0] = 1
    for i in range(N):
        for j in range(N):
            for k in range(S):
                if dp[i][j][k] == 0:
                    continue
                dp[i+1][j][k] += dp[i][j][k]
                dp[i+1][j+1][k+x[i]] += dp[i][j][k]

    M = S//A
    ans = 0
    for i in range(1,N+1):
        if i*A <= S:
            ans += dp[-1][i][i*A]
    
    print(ans)
    
if __name__ == "__main__":
    main()

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
a = [a[i]-k for i in range(n)]
DP = [[0 for i in range(5100)] for j in range(52)]
for i in range(52):
    DP[i][2530] = 1
for i in range(1,n+1):
    for j in range(5050):
        DP[i][j] = DP[i-1][j] + DP[i-1][j-a[i-1]]
print(DP[n][2530]-1)

Solution (Python):

N, M = map(int, input().split())
D = list(map(int, input().split()))
dp = [[0] * 2551 for i in range(51)]
dp[0][0] = 1
for k in D:
    for i in range(49, -1, -1):
        for j in range(2500, -1, -1):
            dp[i+1][j + k] += dp[i][j]

ans = 0
for i in range(1, N+1):
    ans += dp[i][i*M]
print(ans)

Solution (Python):
N, A = [int(_) for _ in input().split()]

MAX_I = 5000
memo = [[0] * MAX_I for _ in range(N + 2)]


def cnv(v):
    return v - A + (MAX_I // 2)


X = [int(_) for _ in input().split()]
for i in range(N):
    offset = X[i] - A
    

    mm = memo[i]
    for j in range(MAX_I):
        if mm[j] > 0:
            memo[i + 1][j + offset] += mm[j]
        memo[i + 1][j] += mm[j]

    memo[i + 1][cnv(X[i])] += 1

print(memo[N][MAX_I//2])

Solution (Python):
N, A = map(int, input().split())

X = [A-int(x) for x in input().split()]
MAX = N*A*2

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

dp[0][N*A] = 1
for i in range(N):
  x = X[i]
  for k in range(MAX+1):
    dp[i+1][k] += dp[i][k]
    if 0 <= k+x <= MAX:
      dp[i+1][k+x] += dp[i][k]
      

print(dp[N][N*A]-1)

Solution (Python):
N, A = map(int, input().split())
X = list(map(int, input().split()))
sum_X = sum(X)
dp = [[[0]*(sum_X+1) for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
  for j in range(N):
    for k in range(sum_X):
      if dp[i][j][k] == 0: continue
      
      dp[i+1][j][k] += dp[i][j][k]
      
      dp[i+1][j+1][k+X[i]] += dp[i][j][k]
ans = 0
for k in range(1, N+1):
  if k*A <= sum_X:
    ans += dp[N][k][k*A]
print(ans)

Solution (Python):
n,a = map(int,input().split())
x = sorted(list(map(lambda y:int(y)-a,input().split())))

sx = max(abs(x[0]),abs(x[-1]))*n

dp = [[0 for _ in range(2*sx+2)] for _ in range(n+1)]
dp[0][0] = 1

for j in range(n):
    for t in range(-sx-1,sx+1):
        if -sx <= t-x[j] and t-x[j] <= sx: 
            dp[j+1][t] = dp[j][t] + dp[j][t-x[j]]
        else:
            dp[j+1][t] = dp[j][t]

print(dp[n][0]-1)

Solution (Python):
n,a=map(int,input().split())
lists=list(map(int,input().split()))
 
for i in range(n):
    lists[i]-=a
answer=0
dp=[[0 for i in range(5001)] for _ in range(51)]


 
for i in range(n+1):
    for j in range(4951):
        if i>=1 and j>=lists[i-1]:
            dp[i][j]=dp[i-1][j-lists[i-1]]+dp[i-1][j]
        if i>=1 and j<lists[i-1]:
            dp[i][j]=dp[i-1][j]
        else:
            if j==2500 and i==0:
                dp[i][j]=1
            elif j!=2500 and i==0:
                dp[i][j]=0
print(dp[n][2500]-1)

Solution (Python):
n, a = map(int, input().split())
l = list(map(int, input().split()))

t = 50*n+1
dp = [[0]*t for _ in range(n+1)]

for i in range(n):
  x = l[i]
  for j in reversed(range(n+1)):
    for k in range(t):
      if dp[j][k] != 0:
        dp[j+1][k+x] += dp[j][k]
  dp[0][x] += 1

ans = 0
for i in range(n):
  ans += dp[i][a*(i+1)]

print(ans)

Solution (Python):
n, a = map(int, input().split())
l = list(map(int, input().split()))

t = 50*n+1
dp = [[0]*t for _ in range(n+1)]

for i in range(n):
  x = l[i]
  for j in reversed(range(n+1)):
    for k in range(t):
      if dp[j][k] != 0:
        dp[j+1][k+x] += dp[j][k]
  dp[0][x] += 1

ans = 0
for i in range(n):
  ans += dp[i][a*(i+1)]

print(ans)

Solution (Python):
N, A = list(map(int, input().split()))
x = list(map(int, input().split()))
X = max(max(x), A)

dp=[[[0 for k in range(N*X+1)] for j in range(N+1)] for i in range(N+1)]

ans = 0
for j in range(N+1):
  for k in range(N+1):
    for s in range(N*X+1):
      if j==0 and k==0 and s==0:
        dp[j][k][s]=1
      elif j>=1 and s<x[j-1]:
        dp[j][k][s] = dp[j-1][k][s]
      elif j>=1 and k>=1 and s>=x[j-1]:
        dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
      else:
        dp[j][k][s] = 0
      if j==N and s==k*A:
        ans = ans + dp[j][k][s]
print(ans-1)

Solution (Python):
n, a = map(int, input().split())
x = list(map(int, input().split()))

dp = [[[0] * (n + 1) for _ in range(2501)] for _ in range(n + 1)]

dp[0][0][0] = 1
for i in range(1, n+1):
    for s in range(2501):
        for k in range(i):
            
            dp[i][s][k] += dp[i-1][s][k]

            
            if s + x[i-1] <= 2500:
                dp[i][s + x[i-1]][k+1] += dp[i-1][s][k]

ans = 0
for k in range(1, n + 1):
    target = k * a
    ans += dp[-1][target][k]
print(ans)

Solution (Python):
n,a=map(int,input().split())
import numpy as np
x=np.array(input().split(),dtype=int)
x-=a
pluslist=[]
minuslist=[]
zerocnt=0
for i in range(len(x)):
  if x[i]==0:
    zerocnt+=1
  elif x[i]>0:
    pluslist.append(x[i])
  else:
    minuslist.append(x[i]*(-1))

dpplus=np.full((sum(pluslist)+1),0,dtype=int)
dpminus=np.full((sum(minuslist)+1),0,dtype=int)
dpplus[0]=1
dpminus[0]=1
for v in pluslist:
  for i in range(len(dpplus)-1,-1,-1):
    if dpplus[i]!=0:
      dpplus[i+v]+=dpplus[i]
for v in minuslist:
  for i in range(len(dpminus)-1,-1,-1):
    if dpminus[i]!=0:
      dpminus[i+v]+=dpminus[i]

ans=2**zerocnt-1
for i in range(1,min(len(dpplus),len(dpminus))):
  ans+=dpplus[i]*dpminus[i]*(2**zerocnt)
  
print(ans)

Solution (Python):
import numpy as np

N, A = map(int, input().split())
x = list(map(int, input().split()))
r = 0
l = 0
for y in x:
    y -= A
    if y < 0:
        l += y
    else:
         r += y

M = r-l+1
dp = np.zeros((N+1,M), dtype='i8')
dp[0][-l] = 1

for i in range(1, N+1):
    for j in range(M):
        dp[i][j] = dp[i-1][j]
        j2 = j-x[i-1]+A
        if 0 <= j2 and j2 < M:
            dp[i][j] += dp[i-1][j2]

print(dp[N][-l]-1)