Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
for i in reversed(range(1, M // N + 1)):
    if M % i == 0:
        print(i)
        exit(0)

Fixed submission:
# ND <= M
# D <= M // N
# DはMの約数


def divisors(n):
    """
    nの約数をO(√n)で列挙する
    """
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


N, M = map(int, input().split())
ans = 0
for D in divisors(M):
    if ans < D <= M // N:
        ans = D
print(ans)
Buggy python submission (verdict: Runtime Error):
from fractions import gcd


def lcm(a, b):
    return int(a * b / gcd(a, b))


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

cumlcm = A[0]
for a in A[1:]:
    cumlcm = lcm(cumlcm, a)
m = cumlcm - 1
f = sum(map(lambda a: m % a if a != 0 else m, A))
print(f)


Fixed submission:
from fractions import gcd


def lcm(a, b):
    return a * b // gcd(a, b)


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

cumlcm = A[0]
for a in A[1:]:
    cumlcm = lcm(cumlcm, a)
m = cumlcm - 1
f = sum(map(lambda a: m % a, A))
print(f)

Buggy python submission (verdict: Runtime Error):
from fractions import gcd


def lcm(a, b):
    return int(a * b / gcd(a, b))


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

cumlcm = A[0]
for a in A[1:]:
    cumlcm = lcm(cumlcm, a)
m = cumlcm - 1
f = sum(map(lambda a: m % a, A))
print(f)


Fixed submission:
from fractions import gcd


def lcm(a, b):
    return a * b // gcd(a, b)


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

cumlcm = A[0]
for a in A[1:]:
    cumlcm = lcm(cumlcm, a)
m = cumlcm - 1
f = sum(map(lambda a: m % a, A))
print(f)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]

cnt = 0
while len(AB) > 0:
    bridges = [0] * (N - 1)
    for a, b in AB:
        for i in range(a - 1, b - 1):
            bridges[i] += 1
    collapse = bridges.index(max(bridges))
    cnt += 1
    AB = list(filter(lambda ab: ab[0] > collapse + 1 or collapse + 1 >= ab[1], AB))
print(cnt)

Fixed submission:
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]

AB.sort(key=lambda ab: ab[1])
removed = list()
for a, b in AB:
    if len(removed) == 0:
        removed.append(b - 1)
    elif a <= removed[-1] < b:
        continue
    else:
        removed.append(b - 1)
print(len(removed))
Buggy python submission (verdict: Time Limit Exceeded):
def factorize2(n):
    """
    nの値を素因数分解し、素因数とその指数をtupleにまとめたリストを返す
    e.g.
    >>> factorize(20)
    [(2, 2), (5, 1)]
    """
    b = 2
    fct = []
    while b * b <= n:
        cnt = 0
        while n % b == 0:
            cnt += 1
            n //= b
        if cnt > 0:
            fct.append((b, cnt))
        b += 1
    if n > 1:
        fct.append((n, 1))
    return fct


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

cnt = 0
for a in A:
    res = factorize2(a)
    if len(res) > 0:
        fct, num = res[0]
        if fct == 2:
            cnt += num
print(cnt)

Fixed submission:
def factorize2(n):
    """
    nの値を素因数分解し、素因数とその指数をtupleにまとめたリストを返す
    e.g.
    >>> factorize(20)
    [(2, 2), (5, 1)]
    """
    b = 2
    fct = []
    while b == 2:
        cnt = 0
        while n % b == 0:
            cnt += 1
            n //= b
        if cnt > 0:
            fct.append((b, cnt))
        b += 1
    if n > 1:
        fct.append((n, 1))
    return fct


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

cnt = 0
for a in A:
    res = factorize2(a)
    if len(res) > 0:
        fct, num = res[0]
        if fct == 2:
            cnt += num
print(cnt)
Buggy python submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(100000)

N = int(input())

memo = [None for _ in range(N + 1)]


def f(n):
    if n == 0:
        return 0
    if memo[n] is not None:
        return memo[n]
    ans = n
    pow = 1
    while pow <= n:
        ans = min(ans, f(n - pow) + 1)
        pow *= 6
    pow = 1
    while pow <= n:
        ans = min(ans, f(n - pow) + 1)
        pow *= 9
    memo[n] = ans
    return ans


print(f(N))

Fixed submission:
import sys

sys.setrecursionlimit(300000)

N = int(input())

memo = [None for _ in range(N + 1)]


def f(n):
    if n == 0:
        return 0
    if memo[n] is not None:
        return memo[n]
    ans = n
    pow = 1
    while pow <= n:
        ans = min(ans, f(n - pow) + 1)
        pow *= 6
    pow = 1
    while pow <= n:
        ans = min(ans, f(n - pow) + 1)
        pow *= 9
    memo[n] = ans
    return ans


print(f(N))

Buggy python submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(60000)

N = int(input())

memo = [None for _ in range(N + 1)]


def f(n):
    if n == 0:
        return 0
    if memo[n] is not None:
        return memo[n]
    ans = n
    pow = 1
    while pow <= n:
        ans = min(ans, f(n - pow) + 1)
        pow *= 6
    pow = 1
    while pow <= n:
        ans = min(ans, f(n - pow) + 1)
        pow *= 9
    memo[n] = ans
    return ans


print(f(N))

Fixed submission:
import sys

sys.setrecursionlimit(300000)

N = int(input())

memo = [None for _ in range(N + 1)]


def f(n):
    if n == 0:
        return 0
    if memo[n] is not None:
        return memo[n]
    ans = n
    pow = 1
    while pow <= n:
        ans = min(ans, f(n - pow) + 1)
        pow *= 6
    pow = 1
    while pow <= n:
        ans = min(ans, f(n - pow) + 1)
        pow *= 9
    memo[n] = ans
    return ans


print(f(N))
Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
d = dict()
for i in range(H):
    for j in range(W):
        d[A[i][j]] = (i, j)
Q = int(input())
LR = [tuple(map(int, input().split())) for _ in range(Q)]
for L, R in LR:
    pow = 0
    while L != R:
        i, j = d[L]
        L += D
        x, y = d[L]
        pow += abs(x - i) + abs(y - j)
    print(pow)


Fixed submission:
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]

d = [None for _ in range(H * W + 1)]
for i in range(H):
    for j in range(W):
        d[A[i][j]] = (i, j)

cumsum = [0 for _ in range(H * W + 1)]
for m in range(1, D + 1):
    i = m
    while i <= H * W:
        if i - D <= 0:
            i += D
            continue
        x1, y1 = d[i - D]
        x2, y2 = d[i]
        dist = abs(x2 - x1) + abs(y2 - y1)
        cumsum[i] = cumsum[i - D] + dist
        i += D

Q = int(input())
LR = [tuple(map(int, input().split())) for _ in range(Q)]
for L, R in LR:
    print(cumsum[R] - cumsum[L])
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
nl = [[] for _ in range(N + 1)]
for _ in range(M):
    L, R, D = map(int, input().split())
    nl[L].append((R, D))
    nl[R].append((L, -D))

seen = [None for _ in range(N + 1)]


def dfs(v, d):
    seen[v] = d
    for next_v, D in nl[v]:
        next_d = d + D
        if seen[next_v] is None:
            dfs(next_v, next_d)
        else:
            if seen[next_v] != next_d:
                print('No')
                exit(0)


for v in range(1, N + 1):  # すべての連結成分に対してDFS
    if seen[v] is None:
        dfs(v, 0)

print('Yes')


Fixed submission:
import sys
sys.setrecursionlimit(300000)

N, M = map(int, input().split())
nl = [[] for _ in range(N + 1)]
for _ in range(M):
    L, R, D = map(int, input().split())
    nl[L].append((R, D))
    nl[R].append((L, -D))

seen = [None for _ in range(N + 1)]


def dfs(v, d):
    seen[v] = d
    for next_v, D in nl[v]:
        next_d = d + D
        if seen[next_v] is None:
            dfs(next_v, next_d)
        else:
            if seen[next_v] != next_d:
                print('No')
                exit(0)


for v in range(1, N + 1):  # すべての連結成分に対してDFS
    if seen[v] is None:
        dfs(v, 0)

print('Yes')
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

s = input()
x, y = map(int, input().split())

arr = list(map(len, s.split('T')))
EW = [arr[ew] for ew in range(0, len(arr), 2)]
NS = [arr[ns] for ns in range(1, len(arr), 2)]

# dp[i][j] := i回目までの移動で座標jにいることができるか
dp = [defaultdict(bool) for i in range(len(EW))]
dp[0][EW[0]] = True
for i in range(1, len(EW)):
    for prev in dp[i - 1].keys():
        dp[i][prev + EW[i]] = True
        dp[i][prev - EW[i]] = True
if not dp[-1][x]:
    print('No')
    exit(0)

dp = [defaultdict(bool) for i in range(len(NS))]
dp[0][NS[0]] = True
dp[0][-NS[0]] = True
for i in range(1, len(NS)):
    for prev in dp[i - 1].keys():
        dp[i][prev + NS[i]] = True
        dp[i][prev - NS[i]] = True
if not dp[-1][y]:
    print('No')
    exit(0)

print('Yes')


Fixed submission:
from collections import defaultdict

s = input()
x, y = map(int, input().split())

arr = list(map(len, s.split('T')))
EW = [arr[ew] for ew in range(0, len(arr), 2)]
NS = [arr[ns] for ns in range(1, len(arr), 2)]

# dp[i][j] := i回目までの移動で座標jにいることができるか
dp = [defaultdict(bool) for i in range(len(EW))]
dp[0][EW[0]] = True
for i in range(1, len(EW)):
    for prev in dp[i - 1].keys():
        dp[i][prev + EW[i]] = True
        dp[i][prev - EW[i]] = True
if not dp[-1][x]:
    print('No')
    exit(0)

if len(NS) > 0:
    dp = [defaultdict(bool) for i in range(len(NS))]
    dp[0][NS[0]] = True
    dp[0][-NS[0]] = True
    for i in range(1, len(NS)):
        for prev in dp[i - 1].keys():
            dp[i][prev + NS[i]] = True
            dp[i][prev - NS[i]] = True
    if not dp[-1][y]:
        print('No')
        exit(0)

print('Yes')
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import permutations

class WarshallFloyd(object):

    def __init__(self, adj):
        """
        ワーシャル・フロイド法によって全頂点間の最短距離を O(|V|^3) で計算する。

        :param adj: 隣接行列 adj[i][j] でi番目の頂点からj番目の頂点へのコストを示す パスがなければINF
        """
        self._dist = adj  # 各頂点間の最短距離 初期値として隣接行列をそのまま用い、[i, i]要素を0に初期化する
        for i in range(len(adj)):
            self._dist[i][i] = 0

        self._solve()

    def _solve(self):
        v_len = len(self._dist)
        for i in range(v_len):  # 経由する頂点
            for j in range(v_len):  # 開始頂点
                for k in range(v_len):  # 終端
                    self._dist[j][k] = min(self._dist[j][k], self._dist[j][i] + self._dist[i][k])

    def distance(self, start, goal):
        return self._dist[start][goal]

    def path(self, start, goal):
        pass


N, M, R = map(int, input().split())
r = list(map(int, input().split()))
adj = [[float('inf') for _ in range(N + 1)] for _ in range(N + 1)]
for _ in range(M):
    A, B, C = map(int, input().split())
    adj[A][B] = C
    adj[B][A] = C

wf = WarshallFloyd(adj)

ans = float('inf')
tours = list(map(list, permutations(r, R)))
for tour in tours:
    cost = 0
    for i in range(1, len(tour)):
        cost += wf.distance(tour[i - 1], tour[i])
    ans = min(ans, cost)
print(ans)

Fixed submission:
from itertools import permutations


class WarshallFloyd(object):

    def __init__(self, adj):
        """
        ワーシャル・フロイド法によって全頂点間の最短距離を O(|V|^3) で計算する。

        :param adj: 隣接行列 adj[i][j] でi番目の頂点からj番目の頂点へのコストを示す パスがなければINF
        """
        self._dist = adj  # 各頂点間の最短距離 初期値として隣接行列をそのまま用い、[i, i]要素を0に初期化する
        for i in range(len(adj)):
            self._dist[i][i] = 0

        self._solve()

    def _solve(self):
        v_len = len(self._dist)
        for i in range(v_len):  # 経由する頂点
            for j in range(v_len):  # 開始頂点
                for k in range(v_len):  # 終端
                    self._dist[j][k] = min(self._dist[j][k], self._dist[j][i] + self._dist[i][k])

    def distance(self, start, goal):
        return self._dist[start][goal]

    def path(self, start, goal):
        pass


N, M, R = map(int, input().split())
r = list(map(int, input().split()))
adj = [[float('inf') for _ in range(N + 1)] for _ in range(N + 1)]
for _ in range(M):
    A, B, C = map(int, input().split())
    adj[A][B] = C
    adj[B][A] = C

wf = WarshallFloyd(adj)

ans = float('inf')
tours = list(map(list, permutations(r, R)))
for tour in tours:
    cost = 0
    for i in range(1, len(tour)):
        cost += wf.distance(tour[i - 1], tour[i])
    ans = min(ans, cost)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
from math import isinf


class Edge(object):

    def __init__(self, src, dst, cost):
        self.src = src
        self.dst = dst
        self.cost = cost


class Dijkstra(object):

    def __init__(self, v_len, edges, start, directed=False):
        """
        ダイクストラ法で最短経路を求める。

        :param v_len: グラフのノード数 通常は|V|、1-indexedなグラフなら |V| + 1
        :param edges: グラフの構造
        :param start: 始点 単一視点最短経路問題として解くので必要
        :param directed: 有向グラフの場合True 隣接行列を対称行列にするかが変わる
        """

        # 隣接行列 (adjacency matrix)
        # adj[i][j] でi番目の頂点からj番目の頂点へのコストを示す パスがなければINF
        self._adj = [[float('inf') for _ in range(v_len)] for _ in range(v_len)]
        for e in edges:
            self._adj[e.src][e.dst] = e.cost
            if not directed:
                self._adj[e.dst][e.src] = e.cost
        self._dist = [float('inf') for i in range(v_len)]  # 始点から各頂点までの最短距離
        self._prev = [float('inf') for i in range(v_len)]  # 最短経路における，その頂点の前の頂点のIDを格納する

        self._solve(start)

    def _solve(self, start):
        # 「最短距離が確定した頂点」に隣接する点からBFSするにあたり、それをどう探すかが問題になる
        # 安直に実装すればここで O(|V|) かかってしまうが、優先度キューを使えば O(log|V|) になる
        self._dist[start] = 0
        q = list()
        heappush(q, (0, start))  # キューの要素は (始点から頂点v_iへの仮の距離, v_iのID)

        while len(q) != 0:
            c, src = heappop(q)
            if self._dist[src] < c:
                continue

            # 隣接行列から隣接するノードを全て調べる = BFS
            for dst in range(len(self._adj)):
                cost = self._adj[src][dst]
                if isinf(cost):
                    continue
                if self._dist[src] + cost < self._dist[dst]:
                    self._dist[dst] = self._dist[src] + cost
                    heappush(q, (self._dist[dst], dst))
                    self._prev[dst] = src

    def distance(self, goal):
        return self._dist[goal]

    def path(self, goal):
        path = list()
        path.append(goal)
        cursor = goal

        while not isinf(self._prev[cursor]):
            path.append(self._prev[cursor])
            cursor = self._prev[cursor]

        return list(reversed(path))


N = int(input())
edges = list()
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    edges.append(Edge(a, b, c))

Q, K = map(int, input().split())
dijkstra = Dijkstra(N + 1, edges, K)
for x, y in [tuple(map(int, input().split())) for _ in range(Q)]:
    print(dijkstra.distance(x) + dijkstra.distance(y))


Fixed submission:
N = int(input())
nl = [list() for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    nl[a].append((b, c))
    nl[b].append((a, c))
Q, K = map(int, input().split())

ans = [-1 for _ in range(N + 1)]
stack = [(K, -1, 0)]  # v, p, c
while len(stack) > 0:
    v, p, c = stack.pop()
    ans[v] = c
    for next_v, next_c in nl[v]:
        if next_v == p:
            continue
        stack.append((next_v, v, c + next_c))
for x, y in [tuple(map(int, input().split())) for _ in range(Q)]:
    print(ans[x] + ans[y])
Buggy python submission (verdict: Time Limit Exceeded):
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))

N = I()
A = [I() for _ in range(N)]

seen = {1}
i = 0
light = 1
while light != 2:
    light = A[light - 1]
    if light in seen:
        print(-1)
        exit(0)
    i += 1
print(i)


Fixed submission:
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))

N = I()
A = [I() for _ in range(N)]

seen = set()
i = 0
light = 1
while light != 2:
    seen.add(light)
    light = A[light - 1]
    if light in seen:
        print(-1)
        exit(0)
    i += 1
print(i)
Buggy python submission (verdict: Runtime Error):
import numpy as np

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

colors = np.array([0 for _ in range(9)])
for a in A:
    if 1 <= a <= 399: colors[0] += 1
    elif 400 <= a <= 799: colors[1] += 1
    elif 800 <= a <= 1199: colors[2] += 1
    elif 1200 <= a <= 1599: colors[3] += 1
    elif 1600 <= a <= 1999: colors[4] += 1
    elif 2000 <= a <= 2399: colors[5] += 1
    elif 2400 <= a <= 2799: colors[6] += 1
    elif 2800 <= a <= 3199: colors[7] += 1
    else: colors[8] += 1

if colors[8] == 0:
    ans = len(colors[colors > 0])
    print(ans, ans)
else:
    legend = colors[8]
    colors = colors[:8]
    v = len(colors[colors > 0])
    print(max(1, v), v + min(legend, 8 - v))


Fixed submission:
import numpy as np

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

colors = np.array([0 for _ in range(9)])
for a in A:
    if 1 <= a <= 399: colors[0] += 1
    elif 400 <= a <= 799: colors[1] += 1
    elif 800 <= a <= 1199: colors[2] += 1
    elif 1200 <= a <= 1599: colors[3] += 1
    elif 1600 <= a <= 1999: colors[4] += 1
    elif 2000 <= a <= 2399: colors[5] += 1
    elif 2400 <= a <= 2799: colors[6] += 1
    elif 2800 <= a <= 3199: colors[7] += 1
    else: colors[8] += 1

if colors[8] == 0:
    ans = len(colors[colors > 0])
    print(ans, ans)
else:
    legend = colors[8]
    colors = colors[:8]
    v = len(colors[colors > 0])
    print(max(1, v), v + legend)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
S += S[0]
for key in ['SS', 'SW', 'WS', 'WW']:
    animals = key
    for i in range(N + 1):
        if i < 1:
            continue
        if animals[i] == 'S':
            if S[i] == 'o':
                animals += animals[-2]
            else:
                animals += 'S' if animals[-2] == 'W' else 'W'
        else:
            if S[i] == 'x':
                animals += animals[-2]
            else:
                animals += 'S' if animals[-2] == 'W' else 'W'
    if animals[0] == animals[-2] and animals[1] == animals[-1]:
        print(animals[:-2])
        exit(0)
print(-1)


Fixed submission:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    S = input()
    for key in ['SS', 'SW', 'WS', 'WW']:
        animals = list(key)
        for i in range(N + 1):
            if i < 1:
                continue
            S_i = S[i] if i < N else S[0]
            if animals[i] == 'S':
                if S_i == 'o':
                    animals += animals[-2]
                else:
                    animals += 'S' if animals[-2] == 'W' else 'W'
            else:
                if S_i == 'x':
                    animals += animals[-2]
                else:
                    animals += 'S' if animals[-2] == 'W' else 'W'
        if animals[0] == animals[-2] and animals[1] == animals[-1]:
            print(''.join(animals[:-2]))
            exit(0)
    print(-1)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7

N, A = MI()
X = LMI()

# dp[i][j][s] := i番目までのカードからj枚を選んで合計がsになる組み合わせの数
dp = [[[0] * (A * N + 1) for _ in range(N + 1)] for _ in range(N)]
for i in range(N):
    dp[i][0][0] = 1
dp[0][1][X[0]] = 1
for i in range(1, N):
    for j in range(1, i + 2):
        for s in range(A * N + 1):
            if s - X[i] < 0:
                dp[i][j][s] = dp[i - 1][j][s]
            else:
                dp[i][j][s] = dp[i - 1][j][s] + dp[i - 1][j - 1][s - X[i]]

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


Fixed submission:
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7

N, A = MI()
X = LMI()

# dp[i][j][s] := i番目までのカードからj枚を選んで合計がsになる組み合わせの数
dp = [[[0] * 2502 for _ in range(N + 2)] for _ in range(N + 1)]
for i in range(N):
    dp[i][0][0] = 1
dp[0][1][X[0]] = 1
for i in range(1, N):
    for j in range(1, i + 2):
        for s in range(A * N + 1):
            if s - X[i] < 0:
                dp[i][j][s] = dp[i - 1][j][s]
            else:
                dp[i][j][s] = dp[i - 1][j][s] + dp[i - 1][j - 1][s - X[i]]

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

Buggy python submission (verdict: Runtime Error):
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7

N, A = MI()
X = LMI()
mx = max(X)

# dp[i][j][s] := i番目までのカードからj枚を選んで合計がsになる組み合わせの数
dp = [[[0] * (N * mx + 1) for _ in range(N + 1)] for _ in range(N)]
for i in range(N):
    dp[i][0][0] = 1
dp[0][1][X[0]] = 1
for i in range(N):
    for j in range(1, i + 2):
        for s in range(N * mx + 1):
            dp[i][j][s] = dp[i - 1][j][s] + dp[i - 1][j - 1][s - X[i]]

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


Fixed submission:
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7

N, A = MI()
X = LMI()

# dp[i][j][s] := i番目までのカードからj枚を選んで合計がsになる組み合わせの数
dp = [[[0] * 2502 for _ in range(N + 2)] for _ in range(N + 1)]
for i in range(N):
    dp[i][0][0] = 1
dp[0][1][X[0]] = 1
for i in range(1, N):
    for j in range(1, i + 2):
        for s in range(A * N + 1):
            if s - X[i] < 0:
                dp[i][j][s] = dp[i - 1][j][s]
            else:
                dp[i][j][s] = dp[i - 1][j][s] + dp[i - 1][j - 1][s - X[i]]

ans = 0
for i in range(1, N + 1):
    ans += dp[N - 1][i][A * i]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = input()
cache = []
for i in range(n-1):
  if s[i] + s[i+1] == 'AC':
    cache.append(i)

for i in range(q):
  l, r = map(int, input().split())
  print(sum(l-1 <= i and i + 1 < r for i in cache))


Fixed submission:
n, q = map(int, input().split())
s = input()
li = [0]
for i in range(1, n):
  incr = 1 if s[i-1] + s[i] == 'AC' else 0
  li.append(li[i-1] + incr)

for i in range(q):
  l, r = map(int, input().split())
  print(li[r-1] - li[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = input()

for i in range(q):
  l, r = map(int, input().split())
  print(s[l-1:r].count('AC'))

Fixed submission:
n, q = map(int, input().split())
s = input()
li = [0]
for i in range(1, n):
  incr = 1 if s[i-1] + s[i] == 'AC' else 0
  li.append(li[i-1] + incr)

for i in range(q):
  l, r = map(int, input().split())
  print(li[r-1] - li[l-1])
Buggy python submission (verdict: Runtime Error):
n = int(input())
h = map(int, input().split())

ans = 0
for i in range(1, n):
  d = h[i] - h[i-1]
  if d > 0:
    ans += d
print(ans)

Fixed submission:
n = int(input())
h = list(map(int, input().split()))
 
ans = h[0]
for i in range(1, n):
  d = h[i] - h[i-1]
  if d > 0:
    ans += d
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = [int(input()) for i in range(n)]

h.sort()
ans = max(h)
for i in range(n-k+1):
  hi = h[i:i+k]
  ans = min(ans, max(hi) - min(hi))
print(ans)

Fixed submission:
n, k = map(int, input().split())
h = [int(input()) for i in range(n)]

h.sort()
ans = max(h)
for i in range(n-k+1):
  ans = min(ans, h[i+k-1] - h[i])
print(ans)