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

import numpy
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,S=mi()
    A=list(mi())
    MOD = 998244353

    f = numpy.poly1d([1])
    for a in A:
        g = [1 if x == 0 else 0 for x in range(a+1)]
        g[-1] = 2
        f *= numpy.poly1d(g)
        
        h = [x % MOD for x in f]
        f = numpy.poly1d(h)


    print(f[S] % MOD)



if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20

class Polynomial:
    def __init__(self,dim=0,const=1):
        self.values = [(dim,const)]
    def __add__(self,other):
        return self.values + other.values


class PolySolver:
    def __init__(self,size):
        self.size = size
        self.f = np.zeros(size, np.int64)
        self.f[0] = 1


    def multiple(self,polynomial,MOD): # const1 * x^dim1 + const2 * x^dim2 + ... をfにかけ合わせる
        new_F = np.zeros(self.size, np.int64)
        for dim,const in polynomial:
            if dim != 0:
                g = np.zeros(self.size, np.int64)
                g[dim:] += self.f[:-dim]
            else:
                g = const * self.f.copy()
            new_F += g

        self.f = new_F
        self.f %= MOD

    
    def get_coefficient(self,dim):
        return self.f[dim]
    
def main():
    N,S=mi()
    A=list(mi())
    MOD = 998244353

    poly = PolySolver(3010)
    for a in A:
        f = Polynomial(const=2) + Polynomial(dim=a)
        poly.multiple(f,MOD)

    print(poly.get_coefficient(S))



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

def solve():
	N, M = map(int, input().split())
	A = [int(input()) for _ in range(M)]

	dp = [0]*(N+1)
	dp[0] = 1
	if 1 in A:
		dp[1] = 0
	else:
		dp[1] = 1

	for i in range(2, N+1):
		if i in A:
			dp[i] = 0
		else:
			dp[i] = dp[i-1] + dp[i-2]

	print(dp[N]%1000000007)

solve()

### FIXED CODE ###

def solve():
	N, M = map(int, input().split())

	dp = [0]*(N+1)
	for _ in range(M):
		a = int(input())
		dp[a] = -1

	dp[0] = 1
	if dp[1]==-1:
		dp[1] = 0
	else:
		dp[1] = 1

	for i in range(2, N+1):
		if dp[i]==-1:
			dp[i] = 0
		else:
			dp[i] = dp[i-1] + dp[i-2]

	print(dp[N]%1000000007)

solve()
### BUGGY CODE ###

s = input()
q = int(input())
tbl = [input().split() for _ in range(q)]
for i in range(q):
    if tbl[i][0] == '1':
        s = s[::-1]
    else:
        if tbl[i][1] == '1':
            s = tbl[i][2]+s
        else:
            s = s+tbl[i][2]
print(s)

### FIXED CODE ###

s = input()
q = int(input())
tbl = [input().split() for _ in range(q)]
cnt = 0
r = []
l = []
for i in range(q-1,-1,-1):
    if tbl[i][0] == '1':
        cnt += 1
    else:
        if (cnt + int(tbl[i][1]))%2 == 1:
            l.append(tbl[i][2])
        else:
            r.append(tbl[i][2])
l = ''.join(l)
if cnt%2 == 1:
    s = s[::-1]
r = ''.join(r[::-1])
print(l+s+r)
### BUGGY CODE ###

n = int(input())
A = [int(x) for x in input().split()]
A1 = [A[2*i] for i in range(int(n/2))]
A2 = [A[2*i+1] for i in range(int(n/2))]
A1_count = [A1.count(A1[i]) for i in range(len(A1))]
A2_count = [A2.count(A2[i]) for i in range(len(A2))]
x= len(A1)+len(A2) - max(A1_count) -max(A2_count)
if (x==0) and (max(A1) == max(A2)):
  print(len(A1))
else:
  print(x)

### FIXED CODE ###

n = int(input())
S = [int(x) for x in input().split()]

S0 = {}
S1 = {}
for i in range(len(S)):
  if i%2 == 0:
    if S[i] not in S0:
      S0[S[i]] =1
    else:
      S0[S[i]] += 1
  else:
    if S[i] not in S1:
      S1[S[i]] =1
    else:
      S1[S[i]] += 1

if max(S0, key = S0.get) != max(S1, key = S1.get):
  Answer = len(S) - max(S0.values()) -max(S1.values())
  print(Answer)
  exit()
      
S0list = sorted(list(S0.values()),reverse = True)
S1list = sorted(list(S1.values()),reverse = True)

S00 = S0list[0]

if len(S0list) == 1:
  S01 = 0
else:
  S01 = S0list[1]
S10 = S1list[0]
if len(S1list) == 1:
  S11 = 0
else:
  S11 = S1list[1]
Answer = min(len(S) - S00 - S11,len(S) - S01 - S10)

print(Answer)
### BUGGY CODE ###

n = int(input())
arr = list(map(int,input().split()))
t = int(input())
while t:
    t-=1
    k,r = map(int,input().split())
    for i in range(n):
        if arr[i] == k:
            arr[i]=r
    print(sum(arr))

### FIXED CODE ###

n = int(input())
arr = list(map(int, input().split()))
su = sum(arr)
lst = [0]*100001
q = int(input())
for i in arr:
    lst[i] += 1
for _ in range(q):
    b, c = map(int, input().split())
    su += (c - b) * lst[b]
    print(su)
    lst[c] += lst[b]
    lst[b] = 0
### BUGGY CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    time = [[[INF] * 4 for __ in range(W)] for _ in range(H)]
    dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = collections.deque()
    for i in range(4):
        q.append((0, x1, y1, i))
        time[x1][y1][i] = 0

    while q:
        t, i, j, d = q.pop()
        timeij = time[i][j]
        if timeij[d] != t: continue
        nt = (t + K - 1) // K * K

        ni, nj = i + dr[d][0], j + dr[d][1]
        if 0 <= ni < H and 0 <= nj < W:
            if C[ni][nj] != '@':
                timeninj = time[ni][nj]
                if timeninj[d] > t + 1:
                    q.append((t + 1, ni, nj, d))
                    timeninj[d] = t + 1

        for nd in range(4):
            if nd == d: continue
            if timeij[nd] > nt:
                if nt == t:
                    q.append((nt, i, j, nd))
                else:
                    q.appendleft((nt, i, j, nd))
                timeij[nd] = nt

    ans = min(time[x2][y2][i] for i in range(4))
    if ans == INF:
        print(-1)
    else:
        print((ans + K - 1) // K)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)


### FIXED CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = collections.deque([(x1, y1)])
    dist[x1][y1] = 0
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] == d + 1: continue
                if dist[ni][nj] < d + 1: break
                dist[ni][nj] = d + 1
                q.append((ni, nj))
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)
### BUGGY CODE ###

# coding: utf-8
# Here your code !
n = int(input())
pool = []
for i in range(n):
    a = input()
    if a not in pool:
        pool.append(a)
    elif a in pool:
        pool.remove(a)
print(len(pool))


### FIXED CODE ###

# coding: utf-8
# Here your code !
n = int(input())
pool = {}
for i in range(n):
    a = int(input())
    if a not in pool:
        pool[a] = True
    else:
       del pool[a]
print(len(pool))
### BUGGY CODE ###

def yo():
    l,r = map(int,input().split())

    a = l*r%2019
    for i in range(l,r) :
        for j in range(i+1,r+1):
            if (a > i*j%2019) :
                a = i*j%2019
                if(a==0) :
                    return a

    return a



print(yo())

### FIXED CODE ###

def yo():
    l,r = map(int,input().split())

    a = l*r%2019
    for i in range(l,r) :
        for j in range(i+1,r+1):
            ij = i*j%2019
            
            if (a > ij) :
                a = ij

            if(a==0) :
                return a

    return a



print(yo())
### BUGGY CODE ###

r1,c1,r2,c2=map(int,input().split())

mod=10**9+7
f=[1]
for i in range(10**6+7):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod

def F(r,c):
  ans=0
  for i in range(r+c+1):
    ans+=2**i
    ans%=mod
  d=0
  s=0
  for i in range(r-1,-1,-1):
    s+=comb((r-i-1)+c,c)
    d+=2**i*s
    s%=mod
    d%=mod
  ans=(ans+(mod-d))%mod
  d=0
  s=0
  for i in range(c-1,-1,-1):
    s+=comb((c-i-1)+r,r)
    d+=2**i*s
    s%=mod
    d%=mod
  ans=(ans+(mod-d))%mod
  return ans

ans=F(r2,c2)+(mod-F(r2,c1-1))+(mod-F(r1-1,c2))+F(r1-1,c1-1)
print(ans%mod)

### FIXED CODE ###

r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
ans=0
for i in range(c1,c2+1):
  d=((r2+1)*f[i+r2+1]%mod)*f[r1]
  d%=mod
  d=(d+(mod-((r1*f[r2+1]%mod)*f[i+r1])%mod))%mod
  d*=pow((((i+1)*f[i]%mod)*f[r1]%mod)*f[r2+1]%mod,mod-2,mod)
  d%=mod
  ans+=d
  ans%=mod
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
import bisect

N,Q = map(int,input().split())
# STX = [list(map(int,input().split())) for _ in range (N)]
STX = []
vals = set()
for _ in range(N):
    s,t,x = map(int,input().split())
    STX.append([max(0,s-x), max(0,t-x), x])
    vals.add(max(0,s-x))
    vals.add(max(0,t-x))
D = [int(input()) for _ in range(Q)]
for d in D:
    vals.add(d)
vals = list(vals)
vals.sort()
L = len(vals)
mapping = [-1]*(L+10)
STX.sort(key=lambda x:x[2])
for s,t,x in STX:
    s1 = bisect.bisect_left(vals, s)
    t1 = bisect.bisect_left(vals, t)
    for i in range(s1, t1):
        if mapping[i]==-1:
            mapping[i] = x
    
for d in D:
    d1 = bisect.bisect_left(vals, d)
    print(mapping[d1])



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
import bisect

N,Q = map(int,input().split())
# STX = [list(map(int,input().split())) for _ in range (N)]
STX = []
vals = set()
for _ in range(N):
    s,t,x = map(int,input().split())
    STX.append((max(0,s-x), max(0,t-x), x))
    vals.add(max(0,s-x))
    vals.add(max(0,t-x))
D = [int(input()) for _ in range(Q)]
for d in D:
    vals.add(d)
vals = list(vals)
vals.sort()
L = len(vals)
mapping = [-1]*(L+1)
imos = [[] for _ in range(L+1)]
STX.sort(key=lambda x:x[2])
priority = 0 
for s,t,x in STX:
    s1 = bisect.bisect_left(vals, s)
    t1 = bisect.bisect_left(vals, t)
    imos[s1].append([1, priority, x])
    imos[t1].append([0, priority, x])
    priority += 1

import heapq
cur = -1
cur_priority = 10**9
que = [(cur_priority, cur)]
valid_priority = [True]*(N+1)
for i in range(L+1):
    for f,p,x in  imos[i]:
        if f:
            heapq.heappush(que, (p, x))
        else:
            valid_priority[p] = False
    
    while que[0][1]!=-1 and valid_priority[que[0][0]]==False:
        heapq.heappop(que)
    mapping[i] = que[0][1]

for d in D:
    d1 = bisect.bisect_left(vals, d)
    print(mapping[d1])
### BUGGY CODE ###

a = input()
A = int(a)
P = 1
W = 10 ** 9 + 7
for i in range(A):
    P = P * (i+1)
P = P % W
print(P)

### FIXED CODE ###

import sys
a = sys.stdin.readline()
A = int(a)
P = 1
I = 1 
W = 10 ** 9 + 7
while I <= A:
    P *= I
    I += 1
    P %= W
print(P)
### BUGGY CODE ###

a = input()
s = map(int, raw_input().split())

l = []

if a % 2 == 0:
	for i in range(a):
		if i % 2 == 1:
			l.insert(0, s[i])
		else:
			l.append(s[i])
else:
	for i in range(a):
		if i % 2 == 0:
			l.insert(0, s[i])
		else:
			l.append(s[i])

for i in l:
	print i,

### FIXED CODE ###

a = input()
s = map(int, raw_input().split())

l1 = []
l2 = []

if a % 2 == 0:
	for i in range(a):
		if i % 2 == 1:
			l2.append(s[i])
		else:
			l1.append(s[i])
else:
	for i in range(a):
		if i % 2 == 0:
			l2.append(s[i])
		else:
			l1.append(s[i])

for i in reversed(l2):
	print i,

for i in l1:
	print i,
### BUGGY CODE ###

import heapq

n, m, s, t = map(int, input().split())

root1 = {}
root2 = {}
   
for i in range(m):
    u, v, a, b = map(int, input().split())
    root1[(u, v)] = a
    root2[(u, v)] = b

def edge(G, x):
    return([(b, G[(a, b)]) for (a, b) in G if a == x] + [(a, G[(a, b)]) for (a, b) in G if b == x])

def min_cost(G, start):
    S = [[0, start]]
    heapq.heapify(S)
    D = [float("inf")] * n
    D[start - 1] = 0
    while len(S) > 0:
        cost, site = heapq.heappop(S)
        if D[site - 1] > cost:
            D[site - 1] = cost
        for (site2, cost2) in edge(G, site):
            if D[site2 - 1] > cost + cost2:
                heapq.heappush(S, [cost + cost2, site2])
    return D

jpy = min_cost(root1, s)
snuke = min_cost(root2, t)
cost = [jpy[i] + snuke[i] for i in range(n)]

for i in range(n):
    print(10 ** 15 - min(cost[i:]))

### FIXED CODE ###

import heapq

n, m, s, t = map(int, input().split())

root1 = []
for i in range(n):
    root1.append({})
root2 = []
for i in range(n):
    root2.append({})
   
for i in range(m):
    u, v, a, b = map(int, input().split())
    root1[u - 1][v] = a
    root1[v - 1][u] = a
    root2[u - 1][v] = b
    root2[v - 1][u] = b

def min_cost(root, start): # 経路の端点を１つ指定して任意の点への最小コストを計算
    S = [[0, start]]
    heapq.heapify(S)
    D = [float("inf")] * n
    D[start - 1] = 0
    while len(S) > 0:
        cost, site = heapq.heappop(S)
        if D[site - 1] < cost:
            continue
        for site2, cost2 in root[site - 1].items():
            if D[site2 - 1] > cost + cost2:
                D[site2 - 1] = cost + cost2
                heapq.heappush(S, [cost + cost2, site2])
    return D

jpy = min_cost(root1, s) # 円で両替地点まで移動する最小コスト
snuke = min_cost(root2, t) # 両替地点からスヌークで移動する最小コスト
cost = [jpy[i] + snuke[i] for i in range(n)] # 両替地点についてループ

minimum_cost = []
temp_min = cost[n - 1]
for i in reversed(range(n)):
    temp_min = min(temp_min, cost[i])
    minimum_cost.append(temp_min)

for i in reversed(range(n)):
    print(10 ** 15 - minimum_cost[i])
### BUGGY CODE ###

#!/usr/bin/env python3
import math
#あらかじめmax(a,b)までinv　を計算する
n,a,b = map(int,input().split())
P = 10**9 + 7
N = max(a,b)+1
inv_t = [0]+[1]
for i in range(2,N):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]
def cmb(n, a, p):
    ans = 1
    for i in range(a):
        ans *= (n-i) * inv_t[i+1] % p
    return ans
#print(cmb(n,a,p),cmb(n,b,p))
print((2**n - 1 - cmb(n,a,P) - cmb(n,b,P))%P)

### FIXED CODE ###

#!/usr/bin/env python3
def fac(n,a):
  ans = 1
  for i in range(n,n-a,-1):
    ans *= i
    ans %= mod
  return ans
def cmb(n, a, mod):
    ans = fac(n,a)
    inv = fac(a,a-1)
    return (ans*pow(inv,mod-2,mod)) % mod

n,a,b = map(int,input().split())
mod = 10**9 + 7
#他人のコードパクったけど高速化の理由不明
"""
def pow(n,b,mod):
  if n == 0: return 1
  if n % 2: return 2 * pow(n//2,b,mod)**2 % mod
  else: return pow(n//2,b,mod)**2 % mod"""
print((pow(2,n,mod) - 1 - cmb(n,a,mod) - cmb(n,b,mod))%mod)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split(" ")))
b = list(map(int,input().split(" ")))
c = list(map(int,input().split(" ")))
alpha = []
for i in range(N):
  list = [number for number in b if number > a[i]]
  alpha.append(list)
beta={}
for i in range(N):
  number = len([x for x in c if x > b[i]])
  beta[b[i]] = number

ans = 0
for i in range(N):
  for x in alpha[i]:
    ans += beta[x]

print(ans)
      

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split(" ")))
b = list(map(int,input().split(" ")))
c = list(map(int,input().split(" ")))
#アルゴリズムわからないけどN log N?
a.sort()
b.sort()
c.sort()

#O(N)?
i,j,k = 0,0,0
ans = 0
while j < N:
  while i < N and a[i]<b[j] :
    i += 1
  while k < N and c[k]<=b[j]:
    k += 1
  ans += i * (N - k)
  j += 1

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

# coding: utf-8
import sys
input = sys.stdin.readline
N,M=map(int,input().split())
A=[0]*M
for i in range(M):
    A[i]=int(input())
#print(A)
def dp(n):
    dp=[0]*(N+1)
    dp[0]=1
    dp[1]=0 if 1 in A else 1
    for i in range(N-1):
        if (i+2) in A:
            dp[i+2]=0
        else:
            dp[i+2]=dp[i+1]+dp[i]
    return dp[n]
print(dp(N)%(10**9+7))

### FIXED CODE ###

# coding: utf-8
import sys
input = sys.stdin.readline
N,M=map(int,input().split())
A=[0]*M
dp=[-1]*(N+1)
for i in range(M):
    tmp=int(input())
    dp[tmp]=0
#print(dp)
dp[0]=1
dp[1]=0 if dp[1]==0 else 1

for i in range(2,N+1):
    if dp[i]!=0:
        dp[i]=dp[i-1]+dp[i-2]
        
print(dp[N]%(10**9+7))
### BUGGY CODE ###

n,k = map(int,input().split())
p = [int(i) for i in input().split()]
ans = []
maxv = max(p)
dp = [i+1 for i in range(maxv+1)]
for i in range(1,maxv+1):
    dp[i] = dp[i-1]+dp[i]
dp = [j/(i+1) for i,j in enumerate(dp)]

maxv = 0
for i in range(n-k+1):
    a = 0
    for j in range(i,i+k):
        a += dp[p[j]-1]
    if maxv < a:
        maxv = a
    
print(maxv)

### FIXED CODE ###

n,k = map(int,input().split())
p = [(int(i)+1)/2 for i in input().split()] #期待値にして格納

#累積和を求める
for i in range(1,n):
    p[i]=p[i-1]+p[i]
mx = p[k-1]
for i in range(k,n):
    a = p[i] - p[i-k]
    if a > mx:
        mx = a
        
print(mx)
### BUGGY CODE ###

def divisor(x):
    i = 1
    d = []
    while i*i <= x:
        if x%i == 0:
            d.append(i)
            d.append(x//i)
        i += 1
    return d

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

ans = 1
for i in range(2):
    for d in divisor(a[i]):
        ct = 0
        for j in a:
            if j%d == 0:
                ct += 1
        if ct >= n-1:
            ans = max(ans, d)

print(ans)


### FIXED CODE ###

def divisor(x):
    i = 1
    d = []
    while i*i <= x:
        if x%i == 0:
            d.append(i)
            d.append(x//i)
        i += 1
    return d

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

ans = 1
for i in range(2):
    for d in divisor(a[i]):
        ct = 0
        for j in a:
            if j%d == 0:
                ct += 1
        if ct >= n-1:
            ans = max(ans, d)

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

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

import sys

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

N, M = MAP()

# (鍵の購入コスト, 開けられる宝箱)
keys = [None] * M
for i in range(M):
    c, _ = MAP()
    # どの宝箱を開けられるのかをbitで持っておく
    s = 0
    for a in [a-1 for a in LIST()]:
        s += 1 << a
    keys[i] = (c, s)

# dp[i][j] := i個目の鍵まで考えて、集合jの宝箱を開けるための最小コスト
dp = list2d(M+1, 1<<N, INF)
dp[0][0] = 0
for i in range(M):
    # 今回の鍵で開けられる宝箱の集合s
    s = keys[i][1]
    c = keys[i][0]
    for j in range(1<<N):
        # 今回の鍵を買わない遷移
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        # 買う遷移：遷移元の開けられる宝箱の集合j | 今回の鍵で開けられる宝箱の集合s
        dp[i+1][j|s] = min(dp[i+1][j|s], dp[i][j]+c)
ans = dp[M][-1]

if ans != INF:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

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

import sys

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

N, M = MAP()

# (鍵の購入コスト, 開けられる宝箱)
keys = [None] * M
for i in range(M):
    c, _ = MAP()
    # どの宝箱を開けられるのかをbitで持っておく
    s = 0
    for a in [a-1 for a in LIST()]:
        s += 1 << a
    keys[i] = (c, s)

# dp[i][j] := i個目の鍵まで考えて、集合jの宝箱を開けるための最小コスト
dp = list2d(M+1, 1<<N, INF)
dp[0][0] = 0
for i in range(M):
    # 今回の鍵で開けられる宝箱の集合s
    s = keys[i][1]
    c = keys[i][0]
    for j in range(1<<N):
        # 今回の鍵を買わない遷移
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        # 買う遷移：遷移元の開けられる宝箱の集合j | 今回の鍵で開けられる宝箱の集合s
        dp[i+1][j|s] = min(dp[i+1][j|s], dp[i][j]+c)
ans = dp[M][-1]

if ans != INF:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

def expected_value(arr):
    return ([sum(range(1, ele+1)) / ele for ele in arr])

n, k = [int(x) for x in input().split()]
arr = list(map(int,input().split()))
sum_tmp = [sum(arr[i:i+k]) for i in range(n - (k - 1))]
max_v = max(sum_tmp)
max_i = sum_tmp.index(max_v)
print(sum(expected_value(arr[max_i:max_i + k])))

### FIXED CODE ###

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

m = sum(arr[0:k])
sump = m

for i in range(1, n-k+1):
    sump = sump - arr[i-1] + arr[i+k-1]
    if m < sump:
        m = sump

ans = (m + k) / 2

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

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

# k = bin(A)
k = A
for i in range(A+1,B+1):
	#print(i)
	k= k^i

# print(bin(k))
print(int(k))

### FIXED CODE ###

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

def f(x):
	if x == 0:
		return 0
	elif x%2==0:
		return int(x/2)%2 ^ x
	else:
		return int((x-1)/2)%2 ^ x-1 ^ x

if A==B:
	print(B)
elif A == 0:
	print(0^f(B))
else:
	print(f(A-1)^f(B))
### BUGGY CODE ###

from bisect import bisect_left
x,y,z,k=map(int,input().split())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=sorted([int(i) for i in input().split()])
ab_max=[]
for i in range(x):
    for j in range(y):
        ab_max.append(a[i]+b[j])
ab_max.sort()
def unti(t_sub):
    global x,y,z,k
    ret=0
    for i in range(x*y):
        h=z-bisect_left(c,t_sub-ab_max[i])
        if h==0 or ret>=k:
            return ret
        else:
            ret+=h
    return ret
l,r=0,ab_max[0]+c[-1]
while r>l+1:
    t=(l+r)//2
    if unti(t)>=k:
        r=t
    else:
        l=t
ans=[]
f=False
for i in range(x*y):
    for j in range(z-1,-1,-1):
        u=ab_max[i]+c[j]
        if u>=r:
            ans.append(u)
        else:
            if j==0:f=True
            break
    if f:
        break
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])


### FIXED CODE ###

import heapq
x,y,z,k=map(int,input().split())
#heapqは小さい順にしか並べられないので、-をつければ大きい順になる
a=sorted([-int(i) for i in input().split()])
b=sorted([-int(i) for i in input().split()])
c=sorted([-int(i) for i in input().split()])
check=set()
ans=[]
heapq.heappush(ans,(a[0]+b[0]+c[0],0,0,0))
check.add((0,0,0))
for i in range(k):
    h=heapq.heappop(ans)
    print(-h[0])
    if h[1]+1<x:
        if (h[1]+1,h[2],h[3]) not in check:
            heapq.heappush(ans,(a[h[1]+1]+b[h[2]]+c[h[3]],h[1]+1,h[2],h[3]))
            check.add((h[1]+1,h[2],h[3]))
    if h[2]+1<y:
        if (h[1],h[2]+1,h[3]) not in check:
            heapq.heappush(ans,(a[h[1]]+b[h[2]+1]+c[h[3]],h[1],h[2]+1,h[3]))
            check.add((h[1],h[2]+1,h[3]))
    if h[3]+1<z:
        if (h[1],h[2],h[3]+1) not in check:
            heapq.heappush(ans,(a[h[1]]+b[h[2]]+c[h[3]+1],h[1],h[2],h[3]+1))
            check.add((h[1],h[2],h[3]+1))
'''
while len(ans)!=0:
    print(heapq.heappop(ans)[0])
'''
### BUGGY CODE ###

import itertools

from operator import mul
from functools import reduce

def comb(r,n):
  r = min(n-r,r)
  if r == 0: return 1
  over = reduce(mul, range(n, n - r, -1))
  under = reduce(mul, range(1,r + 1))
  return over // under

mod = 10**9 + 7

n = int(raw_input())
s = raw_input()

ans = 0

q = []

for a in "abcdefghijklmnopqrstuvwxyz":
  q.append( s.count(a) )

for a in range(1,min(26+1,n+1)):
  #print a
  for x in itertools.combinations(q,a):
    ans += reduce(mul,x)
    ans %= mod

print ans % mod


### FIXED CODE ###

mod = 10**9 + 7

n = int(raw_input())
s = raw_input()

q = []

for a in "abcdefghijklmnopqrstuvwxyz":
  q.append( s.count(a) )

ans = 1

for a in q:
  ans *= (a+1)
  ans %= mod

print ans-1