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

N = int(input())
S = input()
L = [[] for i in range(3)]
for i in range(len(S)):
    if S[i] == 'R':
        L[0].append(i)
    elif S[i] == 'G':
        L[1].append(i)
    else:
        L[2].append(i)
ans = 0

for i in range(3):
    for j in range(3):
        if i == j:
            continue
        for k in range(3):
            if i == k or j == k:
                continue
            sb = 0
            sc = 0
            flgb = 0
            for a in range(len(L[i])):
                flgc = 0
                for b in range(sb, len(L[j])):
                    if L[i][a] <= L[j][b]:
                        if flgb == 0:
                            sb = b
                            flgb = 1
                        for c in range(sc, len(L[k])):
                            if L[j][b] <= L[k][c]:
                                if flgc == 0:
                                    sc = c
                                    flgc = 1
                                if L[j][b] - L[i][a] != L[k][c] - L[j][b]:
                                    ans += 1

print(ans)

### FIXED CODE ###

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

RN = S.count('R')
GN = S.count('G')
BN = S.count('B')

ans = RN * GN * BN

for i in range(N):
    for d in range(N):
        j = i + d
        k = i + 2 * d
        if k >= N:
            break
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            ans -= 1

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

n=int(input())
a=1
b=1
c=1
z=0
while a<=3500:
    b=a
    if z==1:
        break
    while b<=3500:
        if 4*a*b- b*n -a*n !=0:
            c=a*b*n/(4*a*b- b*n -a*n)
            if int(c)==c and c>0:
                print(a, b, int(c)) 
                z=1
                break 
        b+=1
    a+=1


### FIXED CODE ###

n=int(input())
a=1
b=1
c=1
z=0
while a<=3500:
    b=a
    if z==1:
        break
    while b<=3500:
        d=4*a*b- b*n -a*n
        if  d > 0:
            c=a*b*n/(d)
            if int(c)==c:
                print(a, b, int(c)) 
                z=1
                break 
        b+=1
    a+=1
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().rstrip().rsplit()))

ans = 1
for val in A:
    ans *= val

    if ans == 0:
        break

    if ans > 10**18:
        ans = -1

print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().rstrip().rsplit()))
A_dict = {}

for val in A:
    A_dict[val] = A_dict.get(val, 0) + 1

limit = 10**18
ans = 1

if A_dict.get(0, 0) > 0:
    ans = 0
else:
    for val in A_dict:
        ans *= val ** A_dict[val]

        if ans > limit:
            ans = -1
            break

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

import itertools

mod = 1000000007
sum = 0
N = int(input())
A = list(map(int, input().split()))
for v in itertools.combinations(A, 2):
    sum += v[0] * v[1]
print(sum%mod)


### FIXED CODE ###

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

mod = 1000000007
S = {}
S[0] = A[0]
for i in range(1, len(A)):
    S[i] = S[i-1] + A[i]

ans = 0
for i in range(len(A)):
    sum = S[len(S)-1] - S[i]
    ans += A[i] * sum
print(ans%mod)
### BUGGY CODE ###

n=int(input())
P=list(map(int,input().split()))
ans=0
for i in range(n):
    Pl=sorted(P[:i+1])
    if Pl[0]==P[i]:
        ans+=1
print(ans)


### FIXED CODE ###

n=int(input())
P=list(map(int,input().split()))
ans=0
minp=n+1
for i in range(n):
    minp=min(minp,P[i])
    if minp==P[i]:
        ans+=1
print(ans)
### BUGGY CODE ###

N,T = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N)]

dp = [[[0,0] for t in range(T)] for i in range(N+1)]
for i,(a,b) in enumerate(AB):
    for t in range(T-1,-1,-1):
        if dp[i+1][t][0] < dp[i][t][0]: dp[i+1][t][0] = dp[i][t][0]
        if dp[i+1][t][1] < dp[i][t][1]: dp[i+1][t][1] = dp[i][t][1]
        if t+a < T:
            if dp[i+1][t+a][0] < dp[i][t][0] + b: dp[i+1][t+a][0] = dp[i][t][0] + b
            if dp[i+1][t+a][1] < dp[i][t][1] + b: dp[i+1][t+a][1] = dp[i][t][1] + b
        if dp[i+1][t][1] < dp[i][t][0] + b: dp[i+1][t][1] = dp[i][t][0] + b
print(dp[-1][-1][-1])

### FIXED CODE ###

N,T = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N)]

dp0 = {0:0}
dp1 = {0:0}

for i,(a,b) in enumerate(AB):
    _dp0 = {0:0}
    _dp1 = {0:0}
    for k0,v0 in dp0.items():
        if k0 in _dp0:
            _dp0[k0] = max(_dp0[k0], v0)
        else:
            _dp0[k0] = v0
        if k0+a < T:
            if k0+a in _dp0:
                _dp0[k0+a] = max(_dp0[k0+a], v0+b)
            else:
                _dp0[k0+a] = v0+b
        if k0 in _dp1:
            _dp1[k0] = max(_dp1[k0], v0+b)
        else:
            _dp1[k0] = v0+b
    for k1,v1 in dp1.items():
        if k1 in _dp1:
            _dp1[k1] = max(_dp1[k1], v1)
        else:
            _dp1[k1] = v1
        if k1+a < T:
            if k1+a in _dp1:
                _dp1[k1+a] = max(_dp1[k1+a], v1+b)
            else:
                _dp1[k1+a] = v1+b
    dp0 = _dp0
    dp1 = _dp1

print(max(dp1.values()))
### BUGGY CODE ###

H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
A = [[[0,0] for _ in range(W)] for _ in range(H)]
for i in range(H):
    cnt = 0
    for j in range(W):
        if S[i][j]=="#":
            cnt = 0
        else:
            cnt += 1
            A[i][j][0] = cnt
for i in range(H):
    for j in range(W-2,-1,-1):
        A[i][j][0] = 0 if A[i][j][0]==0 else max(A[i][j][0],A[i][j+1][0])
for j in range(W):
    cnt = 0
    for i in range(H):
        if S[i][j]=="#":
            cnt = 0
        else:
            cnt += 1
            A[i][j][1] = cnt
for j in range(W):
    for i in range(H-2,-1,-1):
        A[i][j][1] = 0 if A[i][j][1]==0 else max(A[i][j][1],A[i+1][j][1])
cmax = 0
for i in range(H):
    for j in range(W):
        cmax = max(cmax,sum(A[i][j]))
print(cmax-1)

### FIXED CODE ###

H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
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(W):
        if j==0 and S[i][j]==".":
            L[i][j] = 1
        elif j>0 and S[i][j]==".":
            L[i][j] = L[i][j-1]+1
        if i==0 and S[i][j]==".":
            U[i][j] = 1
        elif i>0 and S[i][j]==".":
            U[i][j] = U[i-1][j]+1
for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if j==W-1 and S[i][j]==".":
            R[i][j] = 1
        elif j<W-1 and S[i][j]==".":
            R[i][j] = R[i][j+1]+1
        if i==H-1 and S[i][j]==".":
            D[i][j] = 1
        elif i>0 and S[i][j]==".":
            D[i][j] = D[i+1][j]+1
cmax = 0
for i in range(H):
    for j in range(W):
        cmax = max(cmax,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)
print(cmax)
### BUGGY CODE ###

n= int(input())

list= list(map(int, input().split()))
cnt=0
for i in range(n):
	listi=list[cnt:]
	a=listi.count(i+1)
	cnt+=a
	print(a)

### FIXED CODE ###

n = int(input())
lis = list(map(int, input().split()))
cnt = [0]*(n)

for i in range(n-1):
	cnt[lis[i]-1]+=1

for i in range(n):
	print(cnt[i])
### BUGGY CODE ###

# def binary_search(lst):
#     pass


import bisect


n = int(input())
lst_A = list(map(int, input().split()))
lst_B = list(map(int, input().split()))
lst_C = list(map(int, input().split()))
lst_A.sort()
lst_B.sort()
lst_C.sort()


ans = 0
for b in lst_B:
    ia = bisect.bisect_left(lst_A, b)
    ic = bisect.bisect_right(lst_C, b)
    na = len(lst_A[:ia])
    nc = len(lst_C[ic:])
    ans += na * nc


print(ans)

### FIXED CODE ###

import bisect


n = int(input())
lst_A = list(map(int, input().split()))
lst_B = list(map(int, input().split()))
lst_C = list(map(int, input().split()))
lst_A.sort()
lst_B.sort()
lst_C.sort()


ans = 0
for b in lst_B:
    na = bisect.bisect_left(lst_A, b)
    nc = n - bisect.bisect_right(lst_C, b)
    ans += na * nc


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

n = int(input())
v = list(map(int,input().split()))
o = v[0::2]
e = v[1::2]
o_s = list(set(o))
e_s = list(set(e))
o_c = [o.count(o_s[i]) for i in range(len(o_s))]
e_c = [e.count(e_s[i]) for i in range(len(e_s))]
if o == e:
  print(int(n/2))
else:
  print(n-max(o_c)-max(e_c))

### FIXED CODE ###

from collections import Counter
n = int(input())
v = list(map(int,input().split()))
o= v[0::2]
e =v[1::2]
o_mode = Counter(o).most_common(2)
e_mode = Counter(e).most_common(2)
if o_mode[0][0] == e_mode[0][0]:
  if len(o_mode) == 1:
    print(int(n/2)) 
  else:
    print(n-max(o_mode[1][1],e_mode[1][1])-o_mode[0][1])
else:
  print(n-o_mode[0][1]-e_mode[0][1])
### BUGGY CODE ###

def main():
    n, p = map(int, input().split())
    if n == 1:
        print(p)
    else:
        ans = 1
        while p % (2**n) == 0:
            ans *= 2
            p //= (2**n)
        for i in range(3, 10**6+1, 2):
            while p % (i**n) == 0:
                ans *= i
                p //= (i**n)
        print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from math import log
def main():
    n, p = map(int, input().split())
    if n == 1:
        print(p)
    else:
        ans = 1
        if n > int(log(p, 2))+2:
            print("1")
            sys.exit()
        if p % (2**n) == 0:
            while p % (2**n) == 0:
                ans *= 2
                p //= (2**n)
        for i in range(3, 10**6+1, 2):
            while p % (i**n) == 0:
                ans *= i
                p //= (i**n)
        print(ans)

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

n, q = map(int, input().split())
s = str(input())
l = []
r = []

for i in range(q):
    l_e, r_e = map(int, input().split())
    l_e -= 1
    l.append(l_e)
    r.append(r_e)

for i in range(q):
    count = 0
    for j in range(l[i], r[i] - 1):
        if s[j] == "A" and s[j+1] == "C":
            count += 1
    print(count)

### FIXED CODE ###

n, q = map(int, input().split())
s = str(input())

count = [0] * n
for i in range(n - 1):
    if s[i:i+2] == "AC":
        count[i+1] = count[i] + 1
    else:
      count[i+1] = count[i]

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

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n-1):
    for j in range(i+2, n):
        if a[i] >= abs(i-j) or a[j] >= abs(i-j): continue
        if abs(i-j) == a[i]+a[j]: ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = []
c = {}

ans = 0
for i in range(n):
    b.append(a[i]+i+1)
    x = -a[i]+i+1
    if x in c:
        c[x] += 1
    else:
        c[x] = 1
for i in range(n):
    if b[i] in c:
        ans += c[b[i]]
print(ans)
### BUGGY CODE ###

import sys

H, W, M = map(int, input().split())
h = [0] * M
w = [0] * M

h_bom = [0] * H
w_bom = [0] * W

for i in range(M):
    h[i], w[i] = map(int, input().split())

    h_bom[h[i] - 1] += 1
    w_bom[w[i] - 1] += 1

h_max = max(h_bom)
w_max = max(w_bom)

h_list = []
w_list = []

for i in range(len(h_bom)):
    if h_bom[i] == h_max:
        h_list.append(i)

for i in range(len(w_bom)):
    if w_bom[i] == w_max:
        w_list.append(i)

for y in h_list:
    for x in w_list:
        flag = True
        for i in range(M):
            if y == (h[i] - 1) and x == (w[i] - 1):
                flag = False

        if flag:
            print(h_max + w_max)
            sys.exit()

print(h_max + w_max - 1)


### FIXED CODE ###

import sys


H, W, M = map(int, input().split())
bomb = [tuple(map(lambda x: int(x) - 1, s.split())) for s in sys.stdin.readlines()]
X = [0] * H  # X:各行の爆破対象の個数
Y = [0] * W  # Y:各列の爆破対象の個数
for h, w in bomb:
    X[h] += 1
    Y[w] += 1
maxX = max(X)
maxY = max(Y)

R = [h for h, x in enumerate(X) if x == maxX]  # R:爆破対象の数が最大となる行の番号
C = [w for w, y in enumerate(Y) if y == maxY]  # C:爆破対象の数が最大となる列の番号

bomb = set(bomb)
for r in R:
    for c in C:
        # (r, c)に爆破対象が存在しないとき, maxX + maxY が答えとなることが確定するため, 
        # 即座に探索を終了する.
        if (r, c) not in bomb:
            print(maxX + maxY)
            exit()
print(maxX + maxY - 1)
### BUGGY CODE ###

s = list(input())
def move_children(RL, li):
    newli = li.copy()
    for n, rl in enumerate(RL):
        if rl == "R":
            newli[n]-=li[n]
            newli[n+1]+=li[n]
        elif rl=="L":
            newli[n]-=li[n]
            newli[n-1]+=li[n]
    return newli
nextli = [1 for i in range(len(s))]
 
for f in range(10**5):
    nextli=move_children(s,nextli)
print(" ".join(map(str,nextli)))

### FIXED CODE ###

s = list(input())
output = [0 for i in s]
ruiseki = 0
for p in range(len(s)):
    if s[p] == "R":
        if s[p+1] == "R":
            ruiseki+=1
        else:
            ruiseki+=1
            output[p] += ruiseki//2 + ruiseki%2
            output[p+1] += ruiseki//2
            ruiseki=0
    
ruiseki = 0
for q in range(len(s)-1, -1, -1):
    if s[q] == "L":
        if s[q-1]=="L":
            ruiseki+=1
        else:
            ruiseki+=1
            output[q] += ruiseki//2 + ruiseki%2
            output[q-1] += ruiseki//2
            ruiseki=0
print(" ".join(map(str,output)))
### BUGGY CODE ###

N,W = input().split()
aArr = list()
ans = 0
tmp = int(N)
for i in range(int(W)):
    inputInt = int(input())
    aArr.append(inputInt)
    if inputInt - tmp == 1:
        print(ans)
        exit()
    tmp = inputInt
tmp = 0
intArr = list()
for i in range(int(N)+1):
    if(i in aArr):
        intArr.append(0)
    elif i < 2:
        intArr.append(1)
    else:
        intArr.append(intArr[i-2] + intArr[i-1])
print(intArr[int(N)] % 1000000007)

### FIXED CODE ###

import sys
N, W = input().split()
aArr = list()
ans = 0
tmp = int(N)
MOD = 10 ** 9 + 7
aArr = set(map(int, sys.stdin))

tmp = 0
tmpB = 0
ans = 1
for i in range(int(N)):
    if (i in aArr):
        tmp = 0
    elif i < 2:
        tmp = 1
    else:
        tmp = ans
    ans = (tmp + tmpB) % MOD
    tmpB = tmp
print(ans)
### BUGGY CODE ###

N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
conunter = [[0] for _ in range(S+1)] #counter[num][numに必要な要素数] = numの組み合わせ数
visited = [0]
conunter[0] = [1]

for k in range(N):
  a = A[k]
  new_count = []
  new_visit = []
  for item in visited:
    if item +a > S:
      continue
    if len(conunter[item+a]) == 1:
      new_visit.append(item+a)
    new_count.append((item + a, tuple(conunter[item])))
  visited.extend(new_visit)
  for new in new_count:
    for k in range(len(new[1])):
      plus = new[1][k]
      if len(conunter[new[0]]) < k+2:
        conunter[new[0]].append(plus)
      else:
        conunter[new[0]][k+1] += plus


two = [1]
for k in range(N):
  two.append(two[-1]*2%mod)


foo = conunter[-1]
ans = 0
for k in range(1, len(foo)): 
  ans = (ans + foo[k]*two[N-k])%mod
print(ans)


### FIXED CODE ###

N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [0 for _ in range(S+1)]
visited = [0]
dp[0] = 1
dp = tuple(dp)
for k in range(N):
  a = A[k]
  nextdp = list(dp)
  nextvisit = []
  for item in visited:
    #process1
    if item + a <= S:
      if nextdp[item+a] == 0:
        nextvisit.append(item+a)
      nextdp[item+a] += dp[item]
      nextdp[item+a] %= mod
    #process2
    if item <= S:
      nextdp[item] += dp[item]
      nextdp[item] %= mod
  dp = tuple(nextdp)
  visited.extend(nextvisit)

print(dp[-1])
### BUGGY CODE ###

import heapq
import math
xs, ys, xt, yt = map(int, input().split())
N = int(input())

Coordinate = {-1: (xs, ys, 0), N:(xt, yt, 0)}
minRadiation = {int(i):10**20 for i in range(-1, N+1)}
ToVisit = {int(i) for i in range(-1, N+1)}
for i in range(N):
    x, y, r = map(int, input().split())
    Coordinate[i] = (x, y, r)

Q = [(0, -1)]
heapq.heapify(Q)
while Q:
    nowRadiation, index = heapq.heappop(Q)
    if index == N:
        print(nowRadiation)
        break
    nowx, nowy, nowr = Coordinate[index]
    for nextIndex in ToVisit:
        nextx, nexty, nextr = Coordinate[nextIndex]
        tempTime = max(0, math.sqrt((nextx-nowx)**2 + (nexty-nowy)**2) - nowr - nextr) + nowRadiation
        if minRadiation[nextIndex] > tempTime:
            minRadiation[nextIndex] = tempTime
            heapq.heappush(Q, (tempTime, nextIndex))


### FIXED CODE ###

import heapq
import math
xs, ys, xt, yt = map(int, input().split())
N = int(input())

Coordinate = {-1: (xs, ys, 0), N:(xt, yt, 0)}
minRadiation = {int(i):10**20 for i in range(-1, N+1)}
ToVisit = {int(i) for i in range(-1, N+1)}
for i in range(N):
    x, y, r = map(int, input().split())
    Coordinate[i] = (x, y, r)

Q = [(0, -1)]
heapq.heapify(Q)
while Q:
    nowRadiation, index = heapq.heappop(Q)
    if index == N:
        print(nowRadiation)
        break
    elif index in ToVisit:
      ToVisit.difference_update({index})
      nowx, nowy, nowr = Coordinate[index]
      for nextIndex in ToVisit:
          nextx, nexty, nextr = Coordinate[nextIndex]
          tempTime = max(0, math.sqrt((nextx-nowx)**2 + (nexty-nowy)**2) - nowr - nextr) + nowRadiation
          if minRadiation[nextIndex] > tempTime:
              minRadiation[nextIndex] = tempTime
              heapq.heappush(Q, (tempTime, nextIndex))
### BUGGY CODE ###

X = int(input())
for a in range(10**9):
    B = a**5 - X
    b = B**-5
    if b % 1 == 0:
        print(str(int(a))+" "+str(int(b)))
        break

### FIXED CODE ###

#D
X = int(input())
for a in range(-200, 200):
    for b in range(-200, 200):
        if a**5 - b**5 == X:
            print(str(a)+" "+str(b))
            break
    if a**5 - b**5 == X:
        break
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
count=0
for i in range(n):
    for j in range(i,n):
        s=sum(a[i:j+1])
        if s%m==0:
            count+=1
print(count)

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
count=0
sum=0
alist=[0]
for i in a:
    sum+=i
    alist.append(sum%m)
alist.sort()
k=-1
n=0
for j in alist:
    if k!=j:
        count+=(n*(n-1)/2)
        n=0
    n+=1
    k=j
count+=(n*(n-1)/2)
print(int(count))
### BUGGY CODE ###

import sys
from collections import defaultdict

h,w,m = map(int, sys.stdin.readline().split())
targets = [tuple(map(lambda x: int(x)-1, sys.stdin.readline().split())) for _ in range(m)]

num_in_h = defaultdict(int)
num_in_w = defaultdict(int)
for t in targets:
    num_in_h[t[0]] += 1
    num_in_w[t[1]] += 1

max_h_set = set(kv[0] for kv in num_in_h.items() if kv[1] == max(num_in_h.values()))
max_w_set = set(kv[0] for kv in num_in_w.items() if kv[1] == max(num_in_w.values()))
ans = max(num_in_h.values()) + max(num_in_w.values())

point = 0
comb = len(max_h_set) * len(max_w_set)
targets = set(targets)
for t in targets:
    if t[0] in max_h_set and t[1] in max_w_set:
        point += 1 # 爆破地点に爆破対象あり

print(ans if comb != point else ans-1)


### FIXED CODE ###

import sys

h,w,m = map(int, sys.stdin.readline().split())
num_in_h = [0] * h
num_in_w = [0] * w
targets = set()
for _ in range(m):
    t_h, t_w = map(lambda x: int(x)-1, sys.stdin.readline().split())
    num_in_h[t_h] += 1
    num_in_w[t_w] += 1
    targets.add((t_h, t_w))

max_h = max(num_in_h)
max_w = max(num_in_w)
max_h_set = set([i for i, v in enumerate(num_in_h) if v == max_h])
max_w_set = set([i for i, v in enumerate(num_in_w) if v == max_w])
ans = max_h + max_w - 1

flag = False
for i in max_h_set:
    for j in max_w_set:
        if (i, j) not in targets:
            flag = True
            break
    if flag: break

print(ans+1 if flag else ans)
### BUGGY CODE ###

import numpy as np
N,M=list(map(int,input().split()))
ans=np.ones(N,int)
for i in range(M):
  L,R=list(map(int,input().split()))
  x=np.zeros(N,int)
  x[L-1:R]=1
  ans*=x
print(sum(ans))

### FIXED CODE ###

N,M=list(map(int,input().split()))
L=[0]*M
R=[0]*M
for i in range(M):
  L[i],R[i]=map(int,input().split())
a=max(L)
b=min(R)
if b>=a:
  print(b-a+1)
else:
  print(0)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
alist=[0]*n
a.sort()
for i in range(n-1):
  if a[i]==a[i+1]:
    alist[i]=1
  for j in range(i+1,n):
    if a[j]%a[i]==0 :
      alist[j]=1
cnt=0
for i in range(n):
  if alist[i]==0:
    cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
m=max(a)
alist=[0]*(m+1)
for i in a:
  for j in range(i,m+1,i):
    alist[j]+=1
cnt=0
for i in a:
  if alist[i]==1:
    cnt+=1
print(cnt)
### BUGGY CODE ###

n, a = map(int, input().split())
cnt = [0]
x = list(map(int, input().split()))
check = [0 for i in range(n)]


def ave(idx, k):
    if idx == n:
        s = 0
        for i in range(n):
            if check[i]:
                s += x[i]

        if s == k * a and k != 0:
            cnt[0] += 1

        return

    ave(idx+1, k)
    check[idx] = 1
    ave(idx+1, k+1)
    check[idx] = 0


def main():
    ave(0, 0)
    print(cnt[0])


if __name__ == '__main__':
    main()


### FIXED CODE ###

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


def ave_comb(v_max, ave):
    dp = [[[0 for c in range(n*v_max+1)] for b in range(n+1)] for a in range(n+1)]

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

    for i in range(1, n+1):
        for j in range(1, i+1):
            for k in range(1, n*v_max+1):
                if k - x[i-1] >= 0:
                    dp[i][j][k] = dp[i-1][j-1][k-x[i-1]] + dp[i-1][j][k]
                else:
                    dp[i][j][k] = dp[i-1][j][k]

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

    return ans


def main():
    x_max = max(max(x), a)

    print(ave_comb(x_max, a))


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

import itertools

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

ans = 0

a_cum = [0] + list(itertools.accumulate(a))
b_cum = [0] + list(itertools.accumulate(b))

for x in range(len(a_cum)):
    for y in range(len(b_cum)):
        if a_cum[x] + b_cum[y] <= k:
            ans = max(ans, x + y)

print(ans)


### FIXED CODE ###

import itertools
import sys

input = sys.stdin.readline

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

ans = 0
a_cum = [0] + list(itertools.accumulate(a))
b_cum = [0] + list(itertools.accumulate(b))

y = m  # len(b_cum) - 1
for x in range(len(a_cum)):
    if a_cum[x] > k:
        break
    while b_cum[y] > k - a_cum[x]:
        y -= 1
    ans = max(ans, x + y)

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

s = input()
t = input()

len_s = len(s)
len_t = len(t)

dp = [[0] * (len_t+1) for _ in range(len_s+1)]

for i in range(len_s):
    for j in range(len_t):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

i = len_s
j = len_t
res = ""
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        res += s[i-1]
        i -= 1
        j -= 1

print(res[::-1])


### FIXED CODE ###

s = input()
t = input()

dp = [[0] * 3010 for _ in range(3010)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

i = len(s)
j = len(t)
res = ""
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        res += s[i-1]
        i -= 1
        j -= 1

ans = ""
for i in reversed(range(len(res))):
    ans += res[i]

print(ans)