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

# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

????????±?????¨??????
"""
import sys
from sys import stdin
input = stdin.readline


C = []
def calc_lcs4(X, Y):
    """
    Y[j]?????¢???????????????????????´
    ?????????????????????????????°?????????????????????????????´
    ????????±?????¨???????????¢??°?????§?¨????????????????????????´
    4/5 ?????????????????????????????¨?????????????????????????????°????????¨??????????????? 5.6?§?
    """
    global C
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)

    C = [[0]*(n+1) for _ in range(m+2)] #  ???????????§??¨???

    max_lcs = 0

    pre_row = C[0]
    for i in range(1, m):
        row = C[i]
        XX = X[i]
        for j, YY in enumerate(Y):
            if XX == YY:
                pr_j1 = pre_row[j - 1]
                row[j] = pr_j1 + 1
                if pr_j1+1 > max_lcs:
                   max_lcs = pr_j1 + 1
            else:
                pr_j = pre_row[j]
                r_j1 = row[j-1]
                if pr_j >= r_j1:
                    row[j] = pr_j
                else:
                    row[j] = r_j1
        pre_row = row

    print(max_lcs)


if __name__ == '__main__':
    num = int(input())

    for _ in range(num):
        X = input().strip()
        Y = input().strip()

        result = calc_lcs4(X, Y)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

最長共通部分列
"""


c = []
def prep_array(X, Y):
    global c
    """ 値が0の2次元配列を用意する。サイズは入力データの最大値を想定して縦横(1000+1)以上必要。 """
    # from array import array
    # c = [array('I', [0] * (len(X)+1)) for _ in range(len(Y)+1)]  #  arrayで用意
    c = [[0]*(len(Y)+2) for _ in range(len(X)+2)] #  リストで用意
    return c


def check_max(array):
    """ 2次元配列の中の最大の値を返す """
    max_lcs = 0
    for row in array:
        temp_max = max(row)
        if temp_max > max_lcs:
            max_lcs = temp_max
    return max_lcs


def calc_lcs4(X, Y, c):
    """
    Y[j]のアクセス方法を変更
    リストの値を一旦変数に保存するように変更
    最長共通部分長を関数内で計算するように変更
    4/5 のテストデータを使用してプロファイリングすると実効時間は 5.6秒
    """
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)
    max_lcs = 0

    pre_row = c[0]
    for i in range(1, m):
        row = c[i]
        XX = X[i]
        for j, YY in enumerate(Y):
            if XX == YY:
                pr_j1 = pre_row[j - 1]
                row[j] = pr_j1 + 1
                if pr_j1+1 > max_lcs:
                   max_lcs = pr_j1 + 1
            else:
                pr_j = pre_row[j]
                r_j1 = row[j-1]
                if pr_j >= r_j1:
                    row[j] = pr_j
                else:
                    row[j] = r_j1
        pre_row = row
    return max_lcs


if __name__ == '__main__':
    # データの入力
    num = int(input())
    #f = open('input.txt')
    #num = int(f.readline())

    for _ in range(num):
        X = input().strip()
        Y = input().strip()

        # 処理の実行
        result = calc_lcs4(X, Y, prep_array(X, Y))

        # 結果の表示
        print(result)
### BUGGY CODE ###

h,n = map(int,input().split())
mg = [list(map(int,input().split())) for i in range(n)]
DP = [[10**18 for i in range(h+1)] for j in range(n+1)]
for i in range(n+1):
  DP[i][0] = 0
for i in range(1,n+1):
  for j in range(1,h+1):
    DP[i][j] = min(DP[i][j],DP[i-1][j])
    DP[i][j] = min(DP[i][j],DP[i][max(0,j-mg[i-1][0])]+mg[i-1][1])
print(DP[-1][-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
h,n = map(int,input().split())
mg = [list(map(int,input().split())) for i in range(n)]
DP = [[10**18 for i in range(h+1)] for j in range(n+1)]
for i in range(n+1):
  DP[i][0] = 0
for i in range(1,n+1):
  for j in range(1,h+1):
    DP[i][j] = min(DP[i][j],DP[i-1][j])
    DP[i][j] = min(DP[i][j],DP[i][max(0,j-mg[i-1][0])]+mg[i-1][1])
print(DP[-1][-1])
### BUGGY CODE ###

n, k = map(int, input().split(" "))
p = list(map(int, input().split(" ")))
max = 0
d = 0
e = 0

for x in range(n - k + 1):
    c = 0
    for y in range(k):
            c += p[x + y]
    if c > max:
        max = c
        d = x

for x in range(k):
    e += (p[d + x] + 1) / 2

print(e)


### FIXED CODE ###

n, k = map(int, input().split(" "))
p = list(map(int, input().split(" ")))
e = []
s = [0]
sj = []

for x in p:
    e.append((1 + x) / 2)

for x in range(n):
    s.append(s[x] + e[x])

for x in range(k, n + 1):
    sj.append(s[x] - s[x - k])
    
print(max(sj))
### BUGGY CODE ###

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]
sum_v = sum(wv[i][1] for i in range(n))
sum_w = sum(wv[i][0] for i in range(n))

dp = [[sum_w + 1] * (sum_v + 1) for i in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for j in range(sum_v + 1):
        if j - wv[i][1] >= 0:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - wv[i][1]] + wv[i][0])
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

ans = 0
for j in range(sum_v + 1):
    if dp[n][j] <= w:
        ans = max(ans, j)
print(ans)

### FIXED CODE ###

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]
sum_v = sum(wv[i][1] for i in range(n))
sum_w = sum(wv[i][0] for i in range(n))

dp = [[sum_w + 1] * (sum_v + 1) for i in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for j in range(sum_v + 1):
        if j - wv[i][1] >= 0:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - wv[i][1]] + wv[i][0])
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

ans = 0
for j in range(sum_v + 1):
    if dp[n][j] <= w:
        ans = max(ans, j)
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
edge = [[] for _ in range(N+1)]
for i in range(M):
    go,to = map(int,input().split())
    edge[go].append(to)
    edge[to].append(go)
count = 0
stack = [[N,0]]
ok = False
for i in range(2*M):
    if stack == []:
        break
    arr = stack.pop(0)
    if arr[1] < 3:
        if arr[0] == 1:
            ok = True
            break
        else:
            for i in edge[arr[0]]:
                stack.append([i,arr[1]+1])
print('POSSIBLE' if ok else 'IMPOSSIBLE')    

### FIXED CODE ###

N,M = map(int,input().split())
edge = []
p = 'POSSIBLE'
i = 'IMPOSSIBLE'
for _ in range(M):
    edge.append(tuple(map(int,input().split())))

from1 = set()
is_reach = False
for go,to in sorted(edge,key=lambda x:x[0]):
    if go == 1:
        from1.add(to)
    else:
        if go in from1 and to == N:
            is_reach = True
            break
print(p if is_reach else i)
### BUGGY CODE ###

from itertools import combinations
N, K = (list)(map(int, input().split()))
pos_x = []
pos_y = []

for _ in range(N):
    a, b = map(int, input().split())
    pos_x.append(a)
    pos_y.append(b)


def count_point(x, y):
    ret = 0
    x_min = min(x)
    x_max = max(x)
    y_min = min(y)
    y_max = max(y)
    for i in range(N):
        if x_min <= pos_x[i] <= x_max and y_min <= pos_y[i] <= y_max:
            ret += 1
    return ret


def calc_area(x, y):
    ret = (x[1]-x[0])*(y[1]-y[0])
    return (abs)(ret)


set_x = set(pos_x)
set_y = set(pos_y)


area = float('inf')
for cand_x in combinations(set_x, 2):
    for cand_y in combinations(set_y, 2):
        if count_point(cand_x, cand_y) >= K:
            area = min(area, calc_area(cand_x, cand_y))
print(area)


### FIXED CODE ###

from itertools import combinations
N, K = (list)(map(int, input().split()))
pos_x = []
pos_y = []

for _ in range(N):
    a, b = map(int, input().split())
    pos_x.append(a)
    pos_y.append(b)


def count_point(x, y):
    ret = 0
    x_min = min(x)
    x_max = max(x)
    y_min = min(y)
    y_max = max(y)
    for i in range(N):
        if x_min <= pos_x[i] <= x_max and y_min <= pos_y[i] <= y_max:
            ret += 1
    return ret


def calc_area(x, y):
    ret = (x[1]-x[0])*(y[1]-y[0])
    return (abs)(ret)


set_x = set(pos_x)
set_y = set(pos_y)


area = float('inf')
for cand_x in combinations(set_x, 2):
    for cand_y in combinations(set_y, 2):
        if count_point(cand_x, cand_y) >= K:
            area = min(area, calc_area(cand_x, cand_y))
print(area)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def I(): return int(input())

result = -1
num = 7
K = I()

if K % 2 == 0 or K %  5 == 0:
    print(-1)
    sys.exit()

for i in range(10**7):
    if num % K == 0:
        print(i+1)
        sys.exit()
    else:
        num += 7*10**(i+1)
        
print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
def I(): return int(input())


def main():
    K = I()
    if K % 2 == 0 or K %  5 == 0:
        print(-1)
        exit()
    if K % 7 == 0:
        K = 9*K//7
    else:
        K = 9*K
    amari = 1
    for i in range(10**6):
        amari = amari*10 % K
        if amari == 1:
            print(i+1)
            exit()
    print(-1)

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

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

if N%2==0:
  for i in range(1,N,2):
    if A.count(i)!=2:
      f = False
else:
  for i in range(2,N,2):
    if A.count(i)!=2:
      f = False

if f:
  print(pow(2,N//2,10**9+7))
else:
  print(0)

### FIXED CODE ###

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

if N%2==0:
  B = [2*(i//2)+1 for i in range(N)]
else:
  B = [2*(i//2) for i in range(1,N+1)]

if A==B:
  print(pow(2,N//2,10**9+7))
else:
  print(0)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

line = input().split(" ")
n = int(line[0])
c = int(line[1])

sushi = []
for _ in range(n):
    line = input().split(" ")
    sushi.append([int(line[0]), int(line[1])]) #[x,v]

ret = 0

r1 = []
r2 = []
state = 0
for i in range(n):
    s = sushi[i]
    state += s[1]
    r1.append(state-2*s[0])
    r2.append(state-s[0])
    if state-s[0]>ret:
        ret = state-s[0]

l1 = []
l2 = []
state = 0
for i in range(n-1,-1,-1):
    s = sushi[i]
    state += s[1]
    l1.append(state-2*(c-s[0]))
    l2.append(state-(c-s[0]))
    if state-(c-s[0])>ret:
        ret = state-(c-s[0])

for (i,r) in enumerate(r1):
    for (j,l) in enumerate(l2):
        if i+j+2>n:
            continue
        if r+l>ret:
            ret = r+l

for (i,l) in enumerate(l1):
    for (j,r) in enumerate(r2):
        if i+j+2>n:
            continue
        if r+l>ret:
            ret = r+l


print(ret)


### FIXED CODE ###

# -*- coding: utf-8 -*-

line = input().split(" ")
n = int(line[0])
c = int(line[1])

sushi = []
for _ in range(n):
    line = input().split(" ")
    sushi.append([int(line[0]), int(line[1])]) #[x,v]

r = []
state = 0
rmax = -9999999999
for i in range(n):
    s = sushi[i]
    state += s[1]

    if state-s[0]>rmax:
        rmax = state-s[0]
    r.append(rmax)

state = 0
ret1 = r[-1]
for i in range(n-1,0,-1):
    s = sushi[i]
    state += s[1]

    s = state-2*(c-s[0]) + r[i-1]
    if s>ret1:
        ret1 = s




l = [0 for _ in range(n)]
state = 0
lmax = -9999999999999
for i in range(n-1,-1,-1):
    s = sushi[i]
    state += s[1]

    if state-(c-s[0])>lmax:
        lmax = state-(c-s[0])
    l[i] = lmax

state = 0
ret2 = l[0]
for i in range(n-1):
    s = sushi[i]
    state += s[1]

    s = state-2*s[0] + l[i+1]
    if s>ret2:
        ret2 = s

print(max(ret1,ret2,0))
### BUGGY CODE ###

import sys
N=int(input())
S=input()

def search_k(k):
  for i in range(N-2*k+1):
    for j in range(i+k,N-k+1):
      for kk in range(k):
        if S[i+kk]!=S[j+kk]:
          break
      else:
        return True
      
  return False

for k in reversed(range(1,N//2+1)):
  if search_k(k):
    print(k)
    break
else:
  print(0)

### FIXED CODE ###

import sys
N=int(input())
S=input()

def z_alg(S):
  N=len(S)
  Z=[N]+[0]*(N-1)
  i,j=1,0
  while i<N:
    while i+j<N and S[j]==S[i+j]:
      j+=1
    if not j:
      i+=1
      continue
    Z[i]=j
    k=1
    while N-i>k and k<j-Z[k]:
      Z[i+k]=Z[k]
      k+=1
    i+=k
    j-=k
  return Z

answer=0
for i in range(N):
  zlist=z_alg(S[i:])
  #print(i,S[i:],zlist)
  for j in range(N-i):
    if j>=zlist[j] and answer<zlist[j]:
      answer=zlist[j]
      
print(answer)
### BUGGY CODE ###

import sys
from collections import Counter
my_input = sys.stdin.readline

H, W, M = map(int, my_input().split())
targets = set()
h_targets = []
w_targets = []

for m in range(M):
    h, w = map(int, my_input().split())
    h, w = h - 1, w - 1
    targets.add((h, w))
    h_targets.append(h)
    w_targets.append(w)

h_counter = Counter(h_targets).most_common()
w_counter = Counter(w_targets).most_common()

h_keys = [k for k, v in h_counter]
w_keys = [k for k, v in w_counter]

ans = 0
highest = h_counter[0][1] + w_counter[0][1]
for hk, hv in h_counter:
    for wk, wv in w_counter:
        if hv + wv < highest:
            break
        ret = highest - ((hk, wk) in targets)
        ans = max(ans, ret)
print(ans)


### FIXED CODE ###

import sys
from collections import Counter
from random import shuffle
my_input = sys.stdin.readline

H, W, M = map(int, my_input().split())
targets = set()
h_targets = []
w_targets = []

for m in range(M):
    h, w = map(int, my_input().split())
    h, w = h - 1, w - 1
    targets.add((h, w))
    h_targets.append(h)
    w_targets.append(w)

h_counter = Counter(h_targets).most_common()
w_counter = Counter(w_targets).most_common()

h_high = h_counter[0][1]
w_high = w_counter[0][1]

h_counter = [[k, v] for k, v in h_counter if v == h_high]
w_counter = [[k, v] for k, v in w_counter if v == w_high]
shuffle(h_counter)
shuffle(w_counter)

highest = h_high + w_high
for hk, hv in h_counter:
    for wk, wv in w_counter:
        if hv + wv < highest:
            break
        if ((hk, wk) not in targets):
            print(highest)
            exit()
print(highest - 1)
### BUGGY CODE ###

# from math import gcd
from fractions import gcd

def lcm(x, y):
    return (x * y) // gcd(x, y)


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

if N > M:
  N, M = M, N
  S, T = T, S

i = 0

while True:
  i += 1
  L = i*lcm(N, M)
  N_list = [(L//N)*k + 1 for k in range(N)]
  M_list = [(L//M)*k + 1 for k in range(M)]

  memo = {}

  for idx, n in enumerate(N_list):
    memo[n] = S[idx]

  for idx, m in enumerate(M_list):
    if m in memo.keys():
      if memo[m] != T[idx]:
        break
  else:
    print(L)
    exit(0)

  if L == N*M:
    break

print(-1)


### FIXED CODE ###

# from math import gcd
from fractions import gcd

def lcm(x, y):
    return (x * y) // gcd(x, y)


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

if N > M:
  N, M = M, N
  S, T = T, S

i = 0

while True:
  i += 1
  L = i*lcm(N, M)
  N_list = [(L//N)*k + 1 for k in range(N)]
  M_list = [(L//M)*k + 1 for k in range(M)]

  # print(N_list)
  # print(M_list)

  memo = {}

  for idx, n in enumerate(N_list):
    memo[n] = S[idx]

  for idx, m in enumerate(M_list):
    if m in memo.keys():
      if memo[m] != T[idx]:
        break
  else:
    print(L)
    exit(0)

  # if L == N*M:
  break

print(-1)
### BUGGY CODE ###

from itertools import combinations

N = int(input())
S = input()
se = set()
for i, j, k in combinations(range(N), 3):
    se.add(S[i] + S[j] + S[k])
print(len(se))

### FIXED CODE ###

N = int(input())
S = input()


def check(subs):
    start = 0
    for x in subs:
        index = S.find(x, start)
        if index == -1:
            return False
        start = index + 1
    return True


ans = 0
for i in range(1000):
    s = '0' * (3 - len(str(i))) + str(i)
    if check(s):
        ans += 1
print(ans)
### BUGGY CODE ###

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

A = [K] * N
answer_list = []

for q in range(Q):
    answer_list.append(int(input()))

for answer in answer_list:
    for n in range(N):
        if n != answer - 1:
            A[n] -= 1

for n in range(N):
    if A[n] > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

import collections

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

if K > Q:
    for n in range(N):
        print("Yes")
else:
    A = [K] * N
    answer_list = []

    for q in range(Q):
        answer_list.append(int(input()))

    answer_list_counts = collections.Counter(answer_list)

    is_clear = [False] * N
    for key in answer_list_counts:
        if K > Q - answer_list_counts[key]:
            is_clear[key - 1] = True


    for n in range(N):
        if is_clear[n]:
            print("Yes")
        else:
            print("No")
### BUGGY CODE ###

import bisect
N = int(input())
X = [int(i) for i in input().split()]
ans = []
for i in range(N):
    num = X.pop(i)
    a = X[:]
    a.sort()
    ans.append(a[(N-1)//2])
    X.insert(i, num)
print(*ans, sep='\n')

### FIXED CODE ###

N = int(input())
X = [int(i) for i in input().split()]
a = X[:]
a.sort()
l = a[N//2-1]
r = a[N//2]
if l == r:
    for i in range(N):
        print(l)
else:
    for i in range(N):
        if X[i] <= l:
            print(r)
        elif X[i] >= r:
            print(l)
### BUGGY CODE ###

h, w = map(int, input().split())
s = []
for i in range(h):
  s.append(input())
  # print(s[i])

r = [[[0, 0] for _ in range(w)] for _ in range(h)]

for i in range(h):
  count = 0
  p = -1
  for j in range(w):
    if s[i][j] == '.':
      count += 1
      if p == -1:
        p = j
    else:
      if not p == -1:
        for k in range(p, j):
          r[i][k][0] = count
        p = -1
        count = 0
  if not p == -1:
    for k in range(p, j+1):
      r[i][k][0] = count

for j in range(w):
  count = 0
  p = -1
  for i in range(h):
    if s[i][j] == '.':
      count += 1
      if p == -1:
        p = i
    else:
      if not p == -1:
        for k in range(p, i):
          r[k][j][1] = count
        p = -1
        count = 0
  if not p == -1:
    for k in range(p, i+1):
      r[k][j][1] = count

ans = 0

for row in r:
  # print(row)
  for e in row:
    t = e[0] + e[1]
    if ans < t:
      ans = t

print(ans-1)

### FIXED CODE ###

h, w = map(int, input().split())
s = []
for i in range(h):
  s.append(input())
  # print(s[i])

l = [[0 for _ in range(w)] for _ in range(h)]
r = [[0 for _ in range(w)] for _ in range(h)]
u = [[0 for _ in range(w)] for _ in range(h)]
d = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
  for j in range(1, w):
    if not s[i][j] == '#' and s[i][j-1] == '.':
      l[i][j] = l[i][j-1] + 1

for i in range(h):
  for j in range(w-2, -1, -1):
    if not s[i][j] == '#' and s[i][j+1] == '.':
      r[i][j] = r[i][j+1] + 1

for j in range(w):
  for i in range(1, h):
    if not s[i][j] == '#' and s[i-1][j] == '.':
      u[i][j] = u[i-1][j] + 1

for j in range(w):
  for i in range(h-2, -1, -1):
    if not s[i][j] == '#' and s[i+1][j] == '.':
      d[i][j] = d[i+1][j] + 1

ret = 0
for i in range(h):
  for j in range(w):
    if not s[i][j] == '#':
      t = l[i][j] + r[i][j] + u[i][j] + d[i][j]
      if ret < t:
        ret = t

print(ret+1)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
MOD = 10 ** 9 + 7
digit = 60
o=[0]*digit
z=[0]*digit

for i in a:
  for j in range(digit):
    if (i >> j) & 1:
      o[j] += 1
    else:
      z[j] += 1
ans = 0
for j in range(digit):
  ans += (o[j]*z[j]*2**j)
print(ans % MOD)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
MOD = 10 ** 9 + 7
digit = 60
o=[0]*digit
z=[0]*digit

for i in a:
  for j in range(digit):
    if (i >> j) & 1:
      o[j] += 1
    else:
      z[j] += 1
ans = 0    
for j in range(digit):
  ans += (o[j]*z[j]*pow(2,j,MOD))
print(ans % MOD)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(input())
for i in range(n):
    print(a.count(str(i+1)))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in a:
    ans[i-1] += 1
for j in ans:
    print(j)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
a = [list(map(int, readline().split())) for _ in range(n)]
for cnt in range(n ** 2):
    check = []
    flag = True
    for i in range(n):
        if a[i]:
            flag = False
            if a[a[i][0] - 1][0] == i + 1:
                check.append(i)
    if flag:
        print(cnt)
        break
    if check:
        for v in check:
            a[v].pop(0)
    else:
        print(-1)
        break


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
a = [list(map(int, readline().split())) for _ in range(n)]
q = list(range(n))
for cnt in range(1, n ** 2 + 2):
    qq = set()
    while q:
        x = q.pop()
        if a[a[x][0] - 1][0] == x + 1:
            qq.add(x)
            qq.add(a[x][0] - 1)
    if qq:
        for x in qq:
            a[x].pop(0)
            if a[x]:
                q.append(x)
    else:
        print(-1)
        break
    if not q:
        print(cnt)
        break
### BUGGY CODE ###

N, A, *x = map(int, open(0).read().split())
max_sum = sum(x)
max_len = len(x)
ans = 0

for i in range(1, 2 ** max_len):
    l = list(map(int, '{0:0>{1:}b}'.format(i, max_len)))
    c = l.count(1)
    s = sum(i * j for i, j in zip(x, l))
    ans += int(s == A * c)
    
print(ans)

### FIXED CODE ###

N, A, *x = map(int, open(0).read().split())

c_nx = N * max(x + [A])
dp = [[[0] * (c_nx + 1) for _ in range(N + 1)] 
      for _ in range(N + 1)]
x = [0] + x

dp[0][0][0] = 1
for j in range(1, N + 1):
    for k in range(N + 1):
        for s in range(c_nx + 1):
            if s < x[j]:
                dp[j][k][s] = dp[j - 1][k][s]
            elif s >= x[j]:
                dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - x[j]]
                
print(sum(dp[N][k][k * A] for k in range(1, N + 1)))
### BUGGY CODE ###

S=list(str(input()))
k=int(input())
for i in range(len(S)):
    si=int(S[i])
    ti=si**(5*10**15)
    if k<=ti:
        print(S[i])
        break
    else:
        k-=ti

### FIXED CODE ###

s = input()
k = int(input())
 
ans = '1'
for i in range(k):
  if s[i] != '1':
    ans = s[i]
    break
 
print(ans)
### BUGGY CODE ###

a = list(map(int, input().split()))
HP = a[0]

x = []
for i in range(a[1]):
    x1, y1 = [int(i) for i in input().split()]
    x.append((x1, y1))

max_tup = max(x, key=lambda x: x[0]) #最高攻撃力の呪文を記憶
max_a = max_tup[0] #その攻撃力を記録
#1次元　横：与えるダメージ　中身：最小魔力
dp = [10**10] * (HP + max_a)  #DP表はHP+最高攻撃力
dp[0] = 0

for i in range(1, len(dp)):
    for a, b in x:
        if i >= a:
            dp[i] = min(dp[i],dp[i - a] + b )

print(min(dp[HP:]))

### FIXED CODE ###

a = list(map(int, input().split()))
HP = a[0]

x = []
for i in range(a[1]):
    x1, y1 = [int(i) for i in input().split()]
    x.append((x1, y1))

max_tup = max(x, key=lambda x: x[0])
max_a = max_tup[0]
dp = [0] * (HP + max_a)

for i in range(1, len(dp)):
    dp[i] = min(dp[i - a] + b for a, b in x)

print(dp[HP])
### BUGGY CODE ###

from collections import deque
N = int(input())
A = deque(map(int, input().split()))
mod = 10**9 + 7
M = len(bin(max(A))) - 2
ans = 0
bitlist = [1]
anslist = [0 for _ in range(M)]
for k in range(M):
    bitlist.append(bitlist[-1]*2%mod)
counter = [0 for _ in range(M)]

for k in range(N):
    a = A.pop()
    c = 0
    while c < M:
        b = a & 1
        if b == 0:
            anslist[c] += counter[-c-1]
        else:
            anslist[c] += k - counter[-c-1]
            counter[-c-1] += 1
        c += 1
        a >>= 1
for k in range(M):
    ans += anslist[k]*bitlist[k]%mod
    ans %= mod
print(ans)




### FIXED CODE ###

from collections import deque
N = int(input())
A = deque(map(int, input().split()))
mod = 10**9 + 7
M = len(bin(max(A))) - 2
ans = 0
bitlist = [1]
for k in range(M):
    bitlist.append(bitlist[-1]*2%mod)
counter = [0 for _ in range(M)]

for k in range(N):
    a = A.pop()
    c = 0
    while c < M:
        b = a & 1
        if b == 0:
            ans += counter[-c-1]*bitlist[c]%mod
            ans %= mod
        else:
            ans += (k-counter[-c-1])*bitlist[c]%mod
            ans %= mod
            counter[-c-1] += 1
        c += 1
        a >>= 1
print(ans)