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

import collections
a,b=map(int,input().split())
c=input()
d=[]
for _ in range(b):
    n,m=map(int,input().split())
    d.append([n,m])
n=len(d)

for i in range(n):
    r=c[d[i][0]-1:d[i][1]]
    print(r.count('AC'))

### FIXED CODE ###

from re import finditer
from bisect import bisect_left
from bisect import bisect_right
a,b=map(int,input().split())
c=input()
d=[]
for _ in range(b):
    n,m=map(int,input().split())
    d.append([n-1,m-1])
n=len(d)
ac1=[m.start() for m in finditer('AC', c)]
ac2=[m.end()-1 for m in finditer('AC', c)]
for i in range(n):
    index1=bisect_left(ac1,d[i][0])
    index2=bisect_right(ac2,d[i][1])
    print(index2-index1)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
    order_F = []
    order_F = input().rstrip().split('T')
    x, y = map(int, input().split())
    vert_DP = [False] * 8001
    side_DP = [False] * 8001
    vert_DP[0] = True
    side_DP[0] = True
    vert_sum = 0
    side_sum = 0
    x -= len(order_F[0])
    for i in range(1, len(order_F)):
        distance = len(order_F[i])
        if i % 2 == 0:
            side_sum += distance
            for j in reversed(range(8001 - distance)):
                if side_DP[j]:
                    side_DP[j + distance] = True
        else:
            vert_sum += distance
            for j in reversed(range(8001 - distance)):
                if vert_DP[j]:
                    vert_DP[j + distance] = True
    if side_sum < x or vert_sum < y:
        print("No")
    elif (side_sum - x) % 2 == 1 or (vert_sum - y) % 2 == 1:
        print("No")
    else:
        if side_DP[(side_sum - x)//2] and vert_DP[(vert_sum - y)//2]:
            print("Yes")
        else:
            print("No")

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
    order_F = []
    order_F = input().rstrip().split('T')
    x, y = map(int, input().split())
    vert_DP = [False] * 8001
    side_DP = [False] * 8001
    vert_DP[0] = True
    side_DP[0] = True
    vert_sum = 0
    side_sum = 0
    distance = [len(order_F[i]) for i in range(len(order_F))]
    order_len = len(order_F)
    x -= len(order_F[0])
    vert_last = 0
    side_last = 0
    for i in range(1, order_len):
        if i % 2 == 0:
            side_sum += distance[i]
            for j in reversed(range(side_last+1)):
                if side_DP[j]:
                    side_DP[j + distance[i]] = True
            side_last += distance[i]
        else:
            vert_sum += distance[i]
            for j in reversed(range(vert_last+1)):
                if vert_DP[j]:
                    vert_DP[j + distance[i]] = True
            vert_last += distance[i]
    if side_sum < x or vert_sum < y:
        print("No")
    elif (side_sum - x) % 2 == 1 or (vert_sum - y) % 2 == 1:
        print("No")
    else:
        if side_DP[(side_sum - x)//2] and vert_DP[(vert_sum - y)//2]:
            print("Yes")
        else:
            print("No")

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

a, b, k = map(int, input().split())
# print(f"{a} {b} {k}")

# l = []
# for i in range(a, b + 1):
#     l.append(i)
# print(l)

# l_small = set()
# for i in range(a, a + k):
#     l_small.add(i)
# print(l_small)

# l_large = set()
# for i in range(b, b - k, -1):
#     l_large.add(i)
# print(l_large)

l = [i for i in range(a, b + 1)]
# print(l)

l_ans = set()
for i in range(len(l)):
    if i + 1 <= k:
        l_ans.add(l[i])
l = sorted(l, reverse=True)
for i in range(len(l)):
    if i + 1 <= k:
        l_ans.add(l[i])
# print(sorted(l_ans))
for num in sorted(l_ans):
    print(num)

### FIXED CODE ###

a, b, k = map(int, input().split())
# print(f"{a} {b} {k}")

# l = []
# for i in range(a, b + 1):
#     l.append(i)
# print(l)

# l_small = set()
# for i in range(a, a + k):
#     l_small.add(i)
# print(l_small)

# l_large = set()
# for i in range(b, b - k, -1):
#     l_large.add(i)
# print(l_large)

# l = [i for i in range(a, b + 1)]
# print(l)

l_ans = set()

count = 1
for i in range(a, b + 1):
    if count <= k:
        l_ans.add(i)
    else:
        break
    count += 1

count = 1
for i in range(b, a - 1, -1):
    if count <= k:
        l_ans.add(i)
    else:
        break
    count += 1

for num in sorted(l_ans):
    print(num)
### BUGGY CODE ###

def longest_subsequence(sequence):
  table = [(1, sequence[0])]
  for x in sequence[1:]:
    maxlen = 0
    for (L, z) in table:
      if z < x: # strict increasing
        maxlen = max(maxlen, L)
    table.append((maxlen+1, x))
  return max(L for (L, _) in table)
def dfs(vertex):
  visited[vertex] = True
  node_sequence.append(a[vertex])
  ans[vertex] = longest_subsequence(node_sequence)
  for node in adjacent[vertex]:
    if not visited[node]:
      dfs(node)
  node_sequence.pop()
  return
n = int(input())
a = list(map(int, input().split()))
adjacent = {i: [] for i in range(n)}
for _ in range(n-1):
  node1, node2 = map(int, input().split())
  node1 -= 1
  node2 -= 1
  adjacent[node1].append(node2)
  adjacent[node2].append(node1)
node_sequence = list()
visited = [False]*n
ans = [0]*n
dfs(0)
[print(value) for value in ans]

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
from bisect import bisect, bisect_left
def longest_subsequence(sequence):
  subsequence = [float("inf") for _ in range(len(sequence)+1)]
  subsequence[0] = float("-inf")
  for value in sequence:
    j = bisect(subsequence, value)
    if subsequence[j-1] != value: # strict increasing
      subsequence[j] = value
  return bisect_left(dp, float("inf"))-1
# print(longest_subsequence([9, 13, 2, 10, 4, 13, 11, 13]))
# sys.exit()
def dfs(vertex):
  visited[vertex] = True
  value = a[vertex]
  j = bisect(subsequence, value)
  previous = subsequence[j]
  if subsequence[j-1] != value: # strict increasing
    subsequence[j] = value
  ans[vertex] = bisect_left(subsequence, float("inf"))-1
  for node in adjacent[vertex]:
    if not visited[node]:
      dfs(node)
  subsequence[j] = previous
  return
n = int(input())
a = list(map(int, input().split()))
adjacent = {i: [] for i in range(n)}
for _ in range(n-1):
  node1, node2 = map(int, input().split())
  node1 -= 1
  node2 -= 1
  adjacent[node1].append(node2)
  adjacent[node2].append(node1)
visited = [False]*n
ans = [0]*n
subsequence = [float("inf") for _ in range(n+1)]
subsequence[0] = float("-inf")
dfs(0)
[print(value) for value in ans]
### BUGGY CODE ###


import numpy as np
N , K ,Q = map(int, input().split())
s = []
for i in range(Q):
    s.append(int(input())-1)
initializer_list = np.full(N,K)
for i in range(len(s)):
    for j in range(len(initializer_list)):
        if j == s[i]:
            pass
        else:
            initializer_list[j] -= 1
for i in range(len(initializer_list)):
    if initializer_list[i] > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

import numpy as np
N , K ,Q = map(int, input().split())
initializer_list = [0] * N
for _ in range(Q):
    i = int(input())-1
    initializer_list[i] += 1
    

[print('Yes') if (Q - initializer_list[i] < K) else print('No')  for i in range(N)]
### BUGGY CODE ###

def main():
    n=int(input())
    aa=list(map(int,input().split()))
    ll={}
    for i,a in enumerate(aa,1):
        x=i-a
        if x not in ll:
            ll[x]=[i]
        else:
            ll[x].append(i)
    c=0
    for i,a in enumerate(aa,1):
        x=i+a
        if x not in ll:
            continue
        c+=sum(j>i for j in ll[x])
    print(c)
main()

### FIXED CODE ###

def main():
    n=int(input())
    aa=list(map(int,input().split()))
    ll={}
    c=0
    for i,a in enumerate(aa,1):
        x=i-a
        if x in ll:
            c+=len(ll[x])
        y=i+a
        if y in ll:
            ll[y].append(i)
        else:
            ll[y]=[i]
    print(c)
main()
### BUGGY CODE ###

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    i = L
    while i < N :
        if None in ANS[i:i+L] :
            while True:
                if ANS[i] :
                    i += 1
                    continue
                else : 
                    ANS[i] = min(Whole[i+1-L:i+1])
                    i += 1
                    break
        else :
            i += L
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.9905
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

n, m = map(int, input().split())
a_list = list(map(int, input().split()))

a_list.sort(reverse=True)
swapped = False
while m > 0:
    a_list[0] = a_list[0] // 2
    m -= 1
    if (n > 1) and (a_list[0] < a_list[1]) and not swapped:
        temp = a_list[0]
        a_list[0] = a_list[1]
        a_list[1] = temp
        swapped = True
    else:
        a_list.sort(reverse=True)
        swapped = False

cost_sum = 0
for a in a_list:
    cost_sum += a

print(cost_sum)


### FIXED CODE ###

from heapq import heappush, heappop

n, m = map(int, input().split())
a_list = list(map(int, input().split()))

hqueue = []
for a in a_list:
    heappush(hqueue, -a)

for i in range(m):
    max_item = -(-heappop(hqueue) // 2)
    heappush(hqueue, max_item)

cost = 0
for i in range(n):
    cost += -heappop(hqueue)

print(cost)
### BUGGY CODE ###

n,x,*a=map(int,open(0).read().split())
ans=0
if a[0]>x:
  ans=a[0]-x
  a[0]=x
for i in range(n-1):
  while a[i+1]+a[i]>x:
    a[i+1]-=1
    ans+=1
print(ans)

### FIXED CODE ###

n,x,*a=map(int,open(0).read().split())
ans=0
if a[0]>x:
  ans=a[0]-x
  a[0]=x
for i in range(n-1):
  if a[i+1]+a[i]>x:
    d=a[i+1]+a[i]-x
    a[i+1]-=d
    ans+=d
print(ans)
### BUGGY CODE ###

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

import math

#L<=i<j<=R
# i*j mod 2019の最小値

if L - R > 2020:
    L = 0
    R = 2019

result = 2019
for i in range(L, R+1):
    for j in range(i+1, R+1):
        tmp = (i * j) % 2019
        result = min(tmp, result)
        
print(result)

### FIXED CODE ###

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

import math

#L<=i<j<=R
# i*j mod 2019の最小値

if R - L > 2030:
    L = 0
    R = 2019

result = 2019
for i in range(L, R+1):
    for j in range(i+1, R+1):
        tmp = (i * j) % 2019
        result = min(tmp, result)
        
print(result)
### BUGGY CODE ###


a = int(input())
s = list(map(int, input().split()))
q = int(input())


while q:
    c, d = map(int, input().split())
    # print(c, d)
    for i in range(len(s)):
        if s[i] == c:
            s[i] = d
    # print(s)
    print(sum(s))

    q -= 1


### FIXED CODE ###


a = int(input())
s = list(map(int, input().split()))
q = int(input())

val = {}

suss = 0
for i in s:
    if i not in val:
        val[i] = 1
    else:
        val[i] += 1

for k, v in val.items():
    suss += k *v

while q:
    c, d = map(int, input().split())
    # print(c, d)
    if c in val:
        if d in val:
            val[d] += val[c]
        else:
            val[d] = val[c]
        suss -= c * val[c]
        suss += d * val[c]
        del val[c]
    # print(val)


    print(suss)

    q -= 1
### BUGGY CODE ###

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

a = 0
b = 0
c = n
ans = c * 1000

while ans < y:
    if y - ans >= 9000:
        a += 1
        c -= 1
    elif y - ans >= 4000:
        b += 1
        c -= 1
    ans = a * 10000 + b * 5000 + c * 1000

if ans != y:
    a = b = c = -1

print(a, b, c)


### FIXED CODE ###

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

a, b, c = (-1, -1, -1)
for i in range(n + 1):
  for j in range(n + 1 - i):
    k = n - (i + j)
    if 10000 * i + 5000 * j + 1000 * k == y:
      a, b, c = (i, j, k)
      break
print(a, b, c)
### BUGGY CODE ###

input()
s=input()
input()
for t in input().split():
  if s.find(t)<0:
    print('NO')
    break
  s=s.replace(t,'',1)
else:
  print('YES')

### FIXED CODE ###

input()
d={}
for k in input().split():
  d[k]=d.get(k,0)+1
input()
for i in input().split():
  if d.get(i,0)>0:
    d[i]-=1
  else:
    print('NO')
    break
else:
  print('YES')
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
#xk=list(map(int,list(xs)))
xj=xs.count("1")

x=int(xs,2)

nmax=2*10**5
xmem=[0]*(nmax+1)
for i in range(n-1,-1,-1):
    xi=x^(1<<i)
    pxi=xj
    if xs[n-1-i]=="0":
        pxi=pxi+1
    else:
        pxi=pxi-1
    if xi==0:
        print(0)
    else:
        xi=xi%pxi
        if xi==0:
            print(1)
        else:
            if xi<nmax and xmem[xi]>0:
                print(xmem[xi])
            else:
                xii=xi
                icnt=1
                while xi>0:
                    icnt+=1
                    xi=xi%(bin(xi).count("1"))
                xmem[xii]=icnt
                print(icnt)


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

for i in range(n-1,-1,-1):
    if xs[n-1-i]=="0":
        pxi=xj+1
        i2=pow(2,i,pxi)
        xi=(xip+i2)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        i2=pow(2,i,pxi)
        xi=(xim-i2)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
        xi=xi%(bin(xi).count("1"))
    print(icnt)
### BUGGY CODE ###

import sys
from sys import stdin
 
input = stdin.readline
sys.setrecursionlimit(10 ** 6)
 
def recursion_j(n, dp, i, j, k):
    if dp[i][j][k] > 0:
        return dp[i][j][k]
    if i == j == k == 0:
        return 0
 
    res = 0
    if i > 0:
        res += recursion_j(n, dp, i - 1, j, k) * i
    if j > 0:
        res += recursion_j(n, dp, i + 1, j - 1, k) * j
    if k > 0:
        res += recursion_j(n, dp, i, j + 1, k - 1) * k
    res += n
    res *= 1 / (i + j + k)
    dp[i][j][k] = res
    return res
 
 
def p_j():
    n = int(input())
    *a, = map(int, input().split())
    c = [0] * 3
    for a_ in a:
        c[a_ - 1] += 1
    dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    print(recursion_j(n, dp, c[0], c[1], c[2]))
    
if __name__ == '__main__':
	p_j()

### FIXED CODE ###

def p_j_dp():
    n = int(input())
    *a, = map(int, input().split())
    c1 = a.count(1)
    c2 = a.count(2)
    c3 = a.count(3)
    dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    for k in range(c3 + 1):
        for j in range(c3 + c2 + 1 - k):
            for i in range(n + 1 - k - j):
                if i + j + k == 0:
                    continue
                res = n
                if i > 0:
                    res += i * dp[i - 1][j][k]
                if j > 0:
                    res += j * dp[i + 1][j - 1][k]
                if k > 0:
                    res += k * dp[i][j + 1][k - 1]
                res /= i + j + k
                dp[i][j][k] = res
    print(dp[c1][c2][c3])
    
p_j_dp()
### BUGGY CODE ###

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

from itertools import combinations

num = 10**9 + 7
ans = 0
for ai, aj in combinations(A, 2):
    ans += ai*aj
    ans %= num
    
print(ans)


### FIXED CODE ###

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

from itertools import combinations

num = 10**9 + 7
ans = 0

B = []
b = 0
for i in reversed(A[1:]):
    b += i
    B.append(b)
B.reverse()
for x, y in zip(A[:-1], B):
    ans += x*y
    ans %= num
print(ans)
### BUGGY CODE ###

import numpy as np
h,w,m = map(int,input().split())
bomb = list(tuple(map(lambda x: int(x)-1,input().split())) for i in range(m))
bombX = [0]*h
bombY = [0]*w
for i,j in bomb:
    bombX[i] += 1
    bombY[j] += 1
maxX = max(bombX)
maxY = max(bombY)
maxX_index = list(i for i in range(h) if bombX[i] == maxX)
maxY_index = list(i for i in range(w) if bombY[i] == maxY)
for i in maxX_index:
    for j in maxY_index:
        if (i,j) not in bomb:
            print(maxX+maxY)
            exit()
print(maxX+maxY-1)

### FIXED CODE ###

h,w,m = map(int,input().split())
bombX = [0]*h
bombY = [0]*w
bomb = set()
maxX = maxY = 0
for i in range(m):
    i,j = map(lambda x:int(x)-1, input().split())
    bomb.add((i,j))
    bombX[i] += 1
    bombY[j] += 1
    maxX = max(maxX,bombX[i])
    maxY = max(maxY,bombY[j])
maxX_index = list(i for i in range(h) if bombX[i] == maxX)
maxY_index = list(i for i in range(w) if bombY[i] == maxY)
for i in maxX_index:
    for j in maxY_index:
        if (i,j) in bomb: continue
        print(maxX+maxY)
        exit()
print(maxX+maxY-1)
### BUGGY CODE ###

import math

Q = int(input())
sosu = [2]

for L in range(3, 10**5, 2): # 2 以外の素数は奇数なので
    for L2 in sosu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosu.append(L)


li = []
for i in range(Q):
    l, r = map(int, input().split())
    li.append((l, r))

for l,r in li:
    ans = 0
    for x in range(l, r+1):
        if x % 2 == 1:
            if x in sosu and (x+1)/2 in sosu:
                ans += 1
    print(ans)

### FIXED CODE ###

import math

Q = int(input())
sosu = [2]

for L in range(3, 10**5, 2): # 2 以外の素数は奇数なので
    for L2 in sosu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosu.append(L)

sosu = set(sosu)

d = {0:0}
now = 0
for x in range(1, 10**5+1):
    if x % 2 == 1:
        if x in sosu and (x+1)/2 in sosu:
            now += 1
    d[x] = now

li = []
for i in range(Q):
    l, r = map(int, input().split())
    li.append((l, r))

for l,r in li:
    ans = 0
    print(d[r]-d[l-1])
### BUGGY CODE ###

import sys

N,K=map(int,input().split())
S=list(input())
MIN=min(S)

def minimum(S):
    T=S+S[::-1]

    ANS=[]

    for i in range(N+1):
        ANS.append(T[i:i+N])

    return min(ANS)

def next(S):
    T=S+S[::-1]
    LIST=[]
    CL=[0]*2*N
    count=0

    for i in range(2*N):
        if T[i]==MIN:
            count+=1

        else:
            count=0

        CL[i]=count

    MAX=max(CL)
    LIST=[]

    for i in range(N-1,2*N):
        if CL[i]==MAX:
            LIST.append(T[i+1-N:i+1])

    return LIST,MAX

def next2(S,x):
    return S[x:]+[MIN]*x,2*x

if K==1:
    print("".join(minimum(S)))

else:
    CAN,MAX=next(S)

    if (MAX<<(K-1))>=N:
        print(MIN*N)
        sys.exit()

    ANS=[]

    for c in CAN:
        x=MAX
        for j in range(K-2):
            c,x=next2(c,x)

            if max(c)==MIN:
                print("".join(c))
                sys.exit()

        ANS.append(minimum(c))

    print("".join(min(ANS)))


### FIXED CODE ###

import sys

N,K=map(int,input().split())
S=list(input())
MIN=min(S)

def minimum(S):
    T=S+S[::-1]

    ANS=[]

    for i in range(N+1):
        ANS.append(T[i:i+N])

    return min(ANS)

def next(S):
    T=S+S[::-1]
    LIST=[]
    CL=[0]*2*N
    count=0

    for i in range(2*N):
        if T[i]==MIN:
            count+=1

        else:
            count=0

        CL[i]=count

    MAX=max(CL)
    LIST=[]

    for i in range(N-1,2*N):
        if CL[i]==MAX:
            LIST.append(T[i+1-N:i+1])

    return LIST,MAX

def next2(S,x):
    return [MIN]*x+S[x:][::-1]

if K==1:
    print("".join(minimum(S)))

else:
    CAN,MAX=next(S)

    if (MAX<<(K-1))>=N:
        print(MIN*N)
        sys.exit()

    ANS=[]

    for c in CAN:

        ANS.append(next2(c,MAX*((1<<(K-1))-1)))

    print("".join(min(ANS)))
### BUGGY CODE ###

N,A=map(int,input().split())
X=[int(a) for a in input().split()]
X.insert(0,0)
ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
dp=[[[0 for i in range(ma+1)] for j in range(N+1)] for k in range(N+1)]
for i in range(N+1):
  dp[i][0][0]=1
for i in range(1,N+1):
  cnt=X[i]
  for j in range(1,N+1):
    for k in range(ma+1):
      if k < cnt:
        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-cnt]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
ans=0
for x in range(1,N+1):
  if x*A<=ma:
    ans+=dp[N][x][x*A]
print(ans)


### FIXED CODE ###

def solve(N,A,X):  
  X.append(0)
  X.sort()
  ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
  dp=[[[0] * (ma+1) for _ in range(N+1)] for _ in range(N+1)]
  
#[x]までの0個を使って0を作る方法は1つ（dp初期化）
  for i in range(N+1):
    dp[i][0][0]=1
  for i in range(1,N+1):
    cnt=X[i]
    for j in range(1,N+1):
      for k in range(ma+1):
        if k < cnt:
          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-cnt]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
  ans=0
  for x in range(1,N+1):
    if x*A<=ma:
      ans+=dp[N][x][x*A]
  return ans

N,A=map(int,input().split())
X=[int(a) for a in input().split()]
ans=solve(N,A,X)
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
expectation=[]
E = []

#期待値
for t in p:
    value = 0
    for x in range(t+1):
        value += x/t
    E.append(value)

for t in range(N-(K-1)):
    value = 0
    for i in range(K):
        value += E[t+i]
    expectation.append(value)

output = sorted(expectation,reverse=True)
print(format(output[0],'.12f'))

### FIXED CODE ###

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

E = []
value=0
#期待値の計算,累積和の計算
for P_i in p:
    value += (1+P_i)/2
    E.append(value)

flag = E[K-1]
#隣接するK項の計算
for k in range(K,N):
    S = E[k] - E[k-K]
    if flag < S:
        flag = S
print(format(flag,'.12f'))
### BUGGY CODE ###

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

dp = [0] * (N+1)
mv = list()
for i in range(K):
    l, r = list(map(int, input().split()))
    for j in range(l, r+1):
        mv.append(j)

def solve(N, dp, mv):
    for i in range(1, N+1):
        for j in range(len(mv)):
            if i+mv[j]>N: break
            if dp[i] == 0: continue
            dp[i+mv[j]] = (dp[i+mv[j]] + dp[i]) % MOD

dp[1] = 1
mv.sort()
solve(N, dp, mv)

print(dp[N])


### FIXED CODE ###

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

a = [0] * (N+1)
f = [0] * (N+1)
mv = list()
for i in range(K):
    mv.append(list(map(int, input().split())))

def solve(N, a, f):
    for i in range(1, N+1):
        f[i] = (f[i-1] + a[i]) % MOD
        for j in range(len(mv)):
            l, r = mv[j]
            if i+l < N+1: a[i+l] = (a[i+l] + f[i]) % MOD
            if i+r+1 < N+1: a[i+r+1] = (a[i+r+1] - f[i]) % MOD

a[1] = 1
mv.sort()
solve(N, a, f)

print(a[N])