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

from collections import deque
import sys
input = sys.stdin.readline


def bellman_ford(N, adj, start):
    ans = [float("inf")] * N
    q = deque()
    q.append((start, 0, 0))
    while len(q):
        i, cost, path = q.popleft()
        if cost >= ans[i]:
            continue
        ans[i] = cost
        for j in adj[i]:
            ncost = cost + adj[i][j]
            if path > N:
                ncost = -float("inf")
            q.append((j, ncost, path+1))
    return ans


def main():
    N, M, P = map(int, input().split())
    adj = [{} for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        if B-1 in adj[A-1]:
            adj[A-1][B-1] = min(P-C, adj[A-1][B-1])
        else:
            adj[A-1][B-1] = P-C
    costs = bellman_ford(N, adj, 0)
    ans = -costs[N-1]
    if ans < 0:
        print(0)
    elif ans == float("inf"):
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline


def bellman_ford(N, adj, start):
    ans = [float("inf")] * N
    q = deque()
    q.append((start, 0, 0))
    while len(q):
        i, cost, path = q.pop()
        if cost >= ans[i]:
            continue
        ans[i] = cost
        for j in adj[i]:
            ncost = cost + adj[i][j]
            if path > N:
                ncost = -float("inf")
            q.append((j, ncost, path+1))
    return ans


def main():
    N, M, P = map(int, input().split())
    adj = [{} for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        if B-1 in adj[A-1]:
            adj[A-1][B-1] = min(P-C, adj[A-1][B-1])
        else:
            adj[A-1][B-1] = P-C
    costs = bellman_ford(N, adj, 0)
    ans = -costs[N-1]
    if ans < 0:
        print(0)
    elif ans == float("inf"):
        print(-1)
    else:
        print(ans)


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

def main():
    X, K, D = map(int, input().split())

    val = [0] * 100000000
    val[0] = X
    #val = X
    #val_new = 0
    if K % 2 == 0 :
        limit = 10
    else :
        limit = 11
    i = 0
    if abs(X) > K * D :
        if X > 0 :
            print(X - K * D)
        else :
            print(abs(X + K * D))
    elif abs(X) == K * D :
        print("0")
    elif D == 0 :
        print(abs(X))
    else :
        for j in val :
            #print(i)
            if abs(val[i] - D) < abs(val[i] + D) :
                val[i+1] = val[i] - D
            else :
                val[i+1] = val[i] + D
            if (val[i+1] == val[i-1]) and i > limit :
                print(abs(val[i + 1]))
                break
            i += 1
            if i == K :
                print(abs(val[i]))
                break


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    X, K, D = map(int, input().split())

    val = [0] * 100000000
    val[0] = X
    #val = X
    #val_new = 0
    if K % 2 == 0 :
        limit = 4
    else :
        limit = 5
    i = 0
    if abs(X) > K * D :
        if X > 0 :
            print(X - K * D)
        else :
            print(abs(X + K * D))
    elif abs(X) == K * D :
        print("0")
    elif X == 0 :
        if limit == 4 :
            print('0')
        else :
            print(abs(D))
    else :
        syo = abs(X) // D
        #print(syo)
        if syo > 3 :
            if X > 0 :
                val[0] = X - (syo-2) * D
            else :
                val[0] = X + (syo - 2) * D
            #print(val[0])
            K = K -(syo-2)
            if K % 2 == 0:
                limit = 2
            else:
                limit = 3
        for j in val :
            #print(i)
            if abs(val[i] - D) < abs(val[i] + D) :
                val[i+1] = val[i] - D
            else :
                val[i+1] = val[i] + D
            #print(val[i+1])
            if (abs(val[i+1]) == abs(val[i-1])) and i > limit :
                #print("a")
                print(abs(val[i + 1]))
                break
            i += 1
            if i == K :
                #print("b")
                print(abs(val[i]))
                break


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

#!/usr/bin/env python3


def main():
    N, A = map(int, input().split())
    x = list(map(int, input().split()))
    X = 50
    dp = [[[0]*(N*X +1) for _ in range(N+1)] for _ in range(N+1)]
    dp[0][0][0] = 1
    for j in range(1,N+1):
        for k in range(N+1):
            for s in range(N*X+1):
                if s >= x[j-1] and k >= 1:
                    dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
                else:# x[j]を選ぶと合計sにできない
                    dp[j][k][s] = dp[j-1][k][s]
    ans = 0
    for i in range(N):
        ans += dp[N][i+1][(i+1)*A]
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3


def main():
    N, A = map(int, input().split())
    x = list(map(int, input().split()))
    X = 50
    dp = [[[0]*(N*X +1) for _ in range(N+1)] for _ in range(N+1)]
    dp[0][0][0] = 1
    for j in range(1,N+1):
        for k in range(N+1):
            for s in range(N*X+1):
                if s >= x[j-1] and k >= 1:
                    dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
                else:# x[j]を選ぶと合計sにできない
                    dp[j][k][s] = dp[j-1][k][s]
    ans = 0
    for i in range(N):
        ans += dp[N][i+1][(i+1)*A]
    print(ans)

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

from sys import stdin
import sys

# A, B, C = [int(x) for x in stdin.readline().rstrip().split()]
# A,B = [int(x) for x in stdin.readline().rstrip().split()]
# U = input().split()
# A, B = [str(x) for x in stdin.readline().rstrip().split()]
N = int(input())
S = list(input())
r = []
g = []
b = []
for i in range(N):
    if S[i] == 'R':
        r.append(i+1)
    elif S[i] == 'G':
        g.append(i+1)
    else:
        b.append(i+1)
# print(r)
# print(g)
# print(b)
cnt = 0
for i in range(len(r)):
    for j in range(len(g)):
        for k in range(len(b)):
            temp = [r[i], g[j], b[k]]
            temp.sort()

            if temp[1]-temp[0] != temp[2]-temp[1]:
                cnt+=1
print(cnt)


### FIXED CODE ###

from sys import stdin
import sys

# A, B, C = [int(x) for x in stdin.readline().rstrip().split()]
# A,B = [int(x) for x in stdin.readline().rstrip().split()]
# U = input().split()
# A, B = [str(x) for x in stdin.readline().rstrip().split()]
N = int(input())
S = list(input())
r = []
g = []
b = []
for i in range(N):
    if S[i] == 'R':
        r.append(i+1)
    elif S[i] == 'G':
        g.append(i+1)
    else:
        b.append(i+1)
# print(r)
# print(g)
# print(b)
cnt = len(r)*len(g)*len(b)
for i in range(N):
    for j in range(i+1, N):
        k = 2*j-i
        if k < N and S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
            cnt -= 1
print(cnt)
### BUGGY CODE ###

S = input()

flag = True

count = 0

while flag:
    M = S
    S = S.replace("BW", "WB", 1)
    if M == S:
        flag = False
    else:
        count += 1

print(count)

### FIXED CODE ###

S = input()

count = 0

BC = 0

for i in range(len(S)):
    S1 = S[i:i+1]
    if S1 == "B":
        BC += 1
    
    if BC > 0 and S1 == "W":
        count += BC

print(count)
### BUGGY CODE ###

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

ans = [(a*i//b) - a*(i//b) for i in range(1, min(b, n)+1)]

print(max(ans))


### FIXED CODE ###

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

if b<=n:
    i = b-1
    ans = (a*i//b) - a*(i//b)
else:
    i = n
    ans = (a*i//b) - a*(i//b)

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

Q = int(input())
LR = []
max = 0

for i in range(Q):
  _input = input().split(' ')
  LR.append((int(_input[0]), int(_input[1])))
  if max < LR[i][1]:
    max = LR[i][1]

num = [True]*(max+1)
num[0] = num[1] = False
for i in range(2,int(max**0.5)+1):
  if num[i]:
    for j in range(i**2, max, i):
      num[j] = False
primeList = [i for i in range(2,max+1) if num[i]]

for i in range(Q):
  sum = 0
  if LR[i][0] % 2 == 0:
    for i in range(LR[i][0]+1, LR[i][1]+1, 2):
      if (i in primeList) and ((i+1)/2 in primeList):
        sum = sum + 1
  else:
    for i in range(LR[i][0], LR[i][1]+1, 2):
      if (i in primeList) and ((i+1)/2 in primeList):
        sum = sum + 1
  print(sum)

### FIXED CODE ###

num = [True]*100001
num[0] = num[1] = False
for i in range(2,317):
  if num[i]:
    for j in range(i**2, 100000, i):
      num[j] = False

c = [0]*100002
for i in range(3, 100001, 2):
  if (num[i]) and (num[int((i+1)/2)]):
    c[i] = c[i] + 1

for i in range(3, 100001):
  c[i] = c[i] + c[i-1]

for i in range(int(input())):
  _input = input().split(' ')
  print(c[int(_input[1])] - c[int(_input[0])-1])
### BUGGY CODE ###

n = int(input())
L = sorted(list(map(int, input().split())), reverse = True)

# c < b < a の条件下
def judge(a:int, b:int, c:int):
    if a < b + c:
        pass
    else:
        return False
    return True

def binary_search(l:int, r:int):
    while r - l > 1:
        mid = (l + r) // 2
        c = L[mid]
        if judge(a, b, c) == True:
            l = mid
        else:
            r = mid
    return l

ans = 0
for i in range(n - 2):
    a = L[i]
    for j in range(i + 1, n - 1):
        b = L[j]
        f1 = judge(a, b, L[j + 1])
        f2 = judge(a, b, L[n - 1])
        if f1 == True:
            if f2 == False:
                ans += binary_search(j, n - 1) - j 
            else:
                ans += n - j - 1
        else:
            pass
    
print(ans)

### FIXED CODE ###

n = int(input())
L = sorted(list(map(int, input().split())), reverse = True)

def judge(a:int, b:int, c:int):
    if a < b + c:
        pass
    else:
        return False
    if b < c + a:
        pass
    else:
        return False
    if c < a + b:
        pass
    else:
        return False
    return True

def binary_search(l:int, r:int):
    while r - l > 1:
        mid = (l + r) // 2
        c = L[mid]
        if judge(a, b, c) == True:
            l = mid
        else:
            r = mid
    return l

ans = 0
for i in range(n - 2):
    a = L[i]
    for j in range(i + 1, n - 1):
        b = L[j]
        f1 = judge(a, b, L[j + 1])
        f2 = judge(a, b, L[n - 1])
        if f1 == True:
            if f2 == False:
                ans += binary_search(j, n - 1) - j 
            else:
                ans += n - j - 1
        else:
            pass
    
print(ans)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
x =[0]*(10**5+1)
a_set =  set(a)
a_list = list(a_set)

a_list.sort()

for i in a_list:
    x[i]=a.count(i)

ans = 0

mi = min(a_list)
mx = max(a_list)

for i in a_list:
    temp = x[i-1]+x[i]+x[i+1]
    if temp>ans:
        ans = temp

print(ans)
    


### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
c =[0]*(10**5+2)


for i in a:
    c[i-1] +=1
    c[i] +=1
    c[i+1] +=1

print(max(c))
### BUGGY CODE ###

def make_Graph(N, edges):#頂点の名前はi - 1で受け付ける
    graph = [ [] for i in range(N)]
    for edge in edges:
        a, b, c = edge
        graph[a].append((b,c))
        graph[b].append((a,c))
    return graph

def BFS(N, graph, start):
    Q = []
    V = []
    d = [float("inf")] * N
    Q.append(start)
    d[start] = 0
    while len(V) < N:
        a = Q.pop(0)
        V.append(a)
        for b, c in graph[a]:
            if not b in V:
                Q.append(b)
                d[b] = d[a] + c
    return d

N = int(input())
graph = [ [] for i in range(N)]
for i in range(N-1):
    a, b, c = (int(j) for j in input().split())
    graph[a-1].append((b-1,c))
    graph[b-1].append((a-1,c))

Q, K =(int(i) for i in input().split())

d = BFS(N, graph, K-1)
for i in range(Q):
    x, y = (int(a) for a in input().split())
    print(d[x-1] + d[y-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline

def make_Graph(N, edges):#頂点の名前はi - 1で受け付ける
    graph = [ [] for i in range(N)]
    for edge in edges:
        a, b, c = edge
        graph[a].append((b,c))
        graph[b].append((a,c))
    return graph

def BFS(N, graph, start):
    Q = []
    V = []
    prev = [None] * N
    dd = [float("inf")] * N
    Q.append(start)
    dd[start] = 0
    while len(V) < N:
        a = Q.pop(0)
        V.append(a)
        for b, c in graph[a]:
            if b != prev[a]:
                Q.append(b)
                prev[b] = a
                dd[b] = dd[a] + c
    return dd

def DFS(N, graph, a, p, d):
    dd[a] = d
    for b, c in graph[a]:
        if b == p or dd[b] != 0:
            continue
        else:
            DFS(N, graph, b, a, d + c)

N = int(input())
graph = [ [] for i in range(N)]
for i in range(N-1):
    a, b, c = (int(j) for j in input().split())
    graph[a-1].append((b-1,c))
    graph[b-1].append((a-1,c))

Q, K =(int(i) for i in input().split())
dd = [0] * N

try:
    DFS(N, graph, K-1, -1, 0)
except:
    dd = BFS(N, graph, K-1)

for i in range(Q):
    x, y = (int(a) for a in input().split())
    print(dd[x-1] + dd[y-1])
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
dic = {}
ans = 0
for i in range(N):
    if A[i] not in dic:
        dic[A[i]] = 1
    else:
        dic[A[i]] += 1
for j in range(len(dic) - K):
    max_k = min(dic, key=dic.get)
    ans += dic.pop(max_k)
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
L = [0]*(200000)
for i in A:
    L[i] += 1

L.sort(reverse=True)
print(sum(L[K:]))
### BUGGY CODE ###

K, S = map(int, input().split())
count = 0

for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if S == x+y+z:
                count += 1

print(count)


### FIXED CODE ###

K, S = map(int, input().split())
count = 0

for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if 0 <= z <= K:
            count += 1

print(count)
### BUGGY CODE ###

s = input()
n = int(input())
normal = 0
for i in range(n):
  li = input().split()
  if int(li[0]) == 1:
    normal ^= 1
  else:
    k = int(li[1]) - 1
    k ^= normal
    if k == 1:
      s += li[2]
    else:
      s = li[2] + s
print(s if normal == 0 else s[::-1])      

### FIXED CODE ###

from collections import deque
s = deque(list(input()))
n = int(input())
normal = 0
for i in range(n):
  li = input().split()
  if int(li[0]) == 1:
    normal ^= 1
  else:
    k = int(li[1]) - 1
    k ^= normal
    if k == 1:
      s.append(li[2])
    else:
      s.appendleft(li[2])
print(''.join(s) if normal == 0 else ''.join(list(s)[::-1]))
### BUGGY CODE ###

#162.C
N,K = map(int,input().split())
X = abs(N-K)
while True:
    if abs(X-K)< X:
        X =abs(X-K)
        continue
    else:
        print(X)
        break

### FIXED CODE ###

#162.C
N,K = map(int,input().split())
a = N//K
if abs(K*(a+1)-N)<abs(K*a-N):
    ans = abs(N - (a+1)*K)
else:
    ans = abs(N-a*K)

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

from fractions import gcd
def lcm(p,q):
    return p*q//gcd(p,q)

n,m = map(int, input().split())
a = list(map(int, input().split()))
x = 1
for i in range(n):
    a[i] = a[i]//2
    x = lcm(x,a[i])
for i in range(n):
    if (x//a[i])%2==0:
        print(0)
        exit()
p = m//x
if p%2==0:
    ans = p//2
else:
    ans = p//2 +1
print(ans)

### FIXED CODE ###

from fractions import gcd
def lcm(p,q):
    return p*q//gcd(p,q)

n,m = map(int, input().split())
a = list(map(int, input().split()))
x = 1
for i in range(n):
    a[i] = a[i]//2
    x = lcm(x,a[i])
    if x>m:
        print(0)
        exit()
for i in range(n):
    if (x//a[i])%2==0:
        print(0)
        exit()
p = m//x
if p%2==0:
    ans = p//2
else:
    ans = p//2 +1
print(ans)
### BUGGY CODE ###

from sys import exit, stdin
N = int(stdin.readline().rstrip())
for i in range(1, 3501):
    for j in range(1, 3501):
            div = 4*i*j-N*i-N*j
            if div <= 0:
                continue
            if (N*i*j) % div == 0:
                print(i, j, (N*i*j) // div)
                exit()

### FIXED CODE ###

from sys import exit, stdin
N = int(stdin.readline().rstrip())
for i in range(1, 3501):
    for j in range(1, 3501):
            div = 4*i*j-N*i-N*j
            if div <= 0:
                continue
            if (N*i*j) % div == 0:
                print(i, j, (N*i*j) // div)
                exit()
### BUGGY CODE ###

h, w = map(int, input().split())
grid = ['#' * (h + 2)]
for _ in range(h):
    grid.append('#' + input() + '#')
grid.append('#' * (h + 2))
lgrid = [[0 for _ in range(w+2)] for _ in range(h+2)]
rgrid = [[0 for _ in range(w+2)] for _ in range(h+2)]
dgrid = [[0 for _ in range(w+2)] for _ in range(h+2)]
ugrid = [[0 for _ in range(w+2)] for _ in range(h+2)]
for i in range(1, h+1):
    for j in range(1, w+1):
        if grid[i][j] == '#':
            lgrid[i][j] = 0
            ugrid[i][j] = 0
        else:
            lgrid[i][j] = lgrid[i][j-1] + 1
            ugrid[i][j] = ugrid[i-1][j] + 1
        if grid[i][w+1-j] == '#':
            rgrid[i][w+1-j] = 0
        else:
            rgrid[i][w+1-j] = rgrid[i][w+2-j] + 1
        if grid[h+1-i][j] == '#':
            dgrid[h+1-i][j] = 0
        else:
            dgrid[h+1-i][j] = dgrid[h+2-i][j] + 1        
cnt = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        tmp = lgrid[i][j]+rgrid[i][j]+ugrid[i][j]+dgrid[i][j] - 3
        cnt = max(cnt, tmp)
print(cnt)


### FIXED CODE ###

h, w = map(int, input().split())
grid = ['#' * (h + 2)]
for _ in range(h):
    grid.append('#' + input() + '#')
grid.append('#' * (h + 2))
lgrid = [[0 for _ in range(w+2)] for _ in range(h+2)]
rgrid = [[0 for _ in range(w+2)] for _ in range(h+2)]
dgrid = [[0 for _ in range(w+2)] for _ in range(h+2)]
ugrid = [[0 for _ in range(w+2)] for _ in range(h+2)]
for i in range(1, h+1):
    for j in range(1, w+1):
        if grid[i][j] == '#':
            lgrid[i][j] = 0
            ugrid[i][j] = 0
        else:
            lgrid[i][j] = lgrid[i][j-1] + 1
            ugrid[i][j] = ugrid[i-1][j] + 1
        if grid[i][w+1-j] == '#':
            rgrid[i][w+1-j] = 0
        else:
            rgrid[i][w+1-j] = rgrid[i][w+2-j] + 1
        if grid[h+1-i][j] == '#':
            dgrid[h+1-i][j] = 0
        else:
            dgrid[h+1-i][j] = dgrid[h+2-i][j] + 1        
cnt = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        tmp = lgrid[i][j]+rgrid[i][j]+ugrid[i][j]+dgrid[i][j] - 3
        cnt = max(cnt, tmp)
print(cnt)
### BUGGY CODE ###

# ncrかなと思うが実験すると1 3 6 10 15 21みたいなのが出てくる
# あらかじめN個作っとくんだけどこれ間に合うん？
# 無理ですね はい  解説

# 愚直にみればそれぞれ選ぶか選ばないかで2通りがn回続く
# a,bの2数も含むとすると、すなわち、2^(n) - 1（かならず1本は選ぶので）。これは繰り返し二乗法で解く。
# ここからa,bを考えたものを引く。具体的にはnCr(n, a) mod p とnCr(n, b) mod pを引く。
# nCr mod pで間に合わんやんけと思って諦めたけどよくよく読んだら条件はa = min(n, 2*10^5)なので間に合うやんけ
# nCrの式変形で分母と分子をそれぞれ作ってやるっていう愚直なやつでもいけるんじゃねこれ

n, a, b = map(int, input().split())
MOD = 10**9 + 7


# 繰り返し二乗法
def repMod(a, n, p):
    if n == 1:
        return a % p
    if n % 2 == 1:
        return a * repMod(a, n - 1, p) % p
    ret = repMod(a, n // 2, p) % p
    return (ret * ret) % p


all_comb = repMod(2, n, MOD)
# nCr = n!/(r!(n-r)!) ゆえ ((n-r+1) * (n-r+2) * .. * n)/(1*2*3*..*r)
# これがr = min(n, 2*10^5)なので愚直にやっても間に合う


def nCrMod(n, r, p):
    ret = 1
    # 分子
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret %= p
    # 分母
    for i in range(2, r + 1):
        # ret //= i なんかこれがおかしい（なんでだろうね）
        ret *= repMod(i, p - 2, p)  # なぜかここでやらないと駄目だった
        ret %= p
    # ret = repMod(ret, p - 2, p) # なぜかここでやると駄目だった
    return ret % p


print((all_comb - nCrMod(n, a, MOD) - nCrMod(n, b, MOD) - 1) % MOD)


### FIXED CODE ###

# ncrかなと思うが実験すると1 3 6 10 15 21みたいなのが出てくる
# あらかじめN個作っとくんだけどこれ間に合うん？
# 無理ですね はい  解説

# 愚直にみればそれぞれ選ぶか選ばないかで2通りがn回続く
# a,bの2数も含むとすると、すなわち、2^(n) - 1（かならず1本は選ぶので）。これは繰り返し二乗法で解く。
# ここからa,bを考えたものを引く。具体的にはnCr(n, a) mod p とnCr(n, b) mod pを引く。
# nCr mod pで間に合わんやんけと思って諦めたけどよくよく読んだら条件はa = min(n, 2*10^5)なので間に合うやんけ
# nCrの式変形で分母と分子をそれぞれ作ってやるっていう愚直なやつでもいけるんじゃねこれ

n, a, b = map(int, input().split())
MOD = 10**9 + 7


# 繰り返し二乗法
def repMod(a, n, p):
    if n == 1:
        return a % p
    if n % 2 == 1:
        return a * repMod(a, n - 1, p) % p
    ret = repMod(a, n // 2, p) % p
    return (ret * ret) % p


all_comb = repMod(2, n, MOD)
# nCr = n!/(r!(n-r)!) ゆえ ((n-r+1) * (n-r+2) * .. * n)/(1*2*3*..*r)
# これがr = min(n, 2*10^5)なので愚直にやっても間に合う


def nCrMod(n, r, p):
    ret = 1
    # 分子
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret %= p
    # 分母
    for i in range(2, r + 1):
        # ret //= i なんかこれがおかしい（なんでだろうね）
        ret *= repMod(i, p - 2, p)  # なぜかここでやらないと駄目だった
        ret %= p
    # ret = repMod(ret, p - 2, p) # なぜかここでやると駄目だった
    return ret % p


print((all_comb - nCrMod(n, a, MOD) - nCrMod(n, b, MOD) - 1) % MOD)
### BUGGY CODE ###

import numpy as np
n = int(input())
a= list(map(int,input().split()))

ans = a[0]

for i in range(1,n):
    if a[i] == 0:
        print("0")
        exit()
    else:
        ans *= a[i]

if ans > 10**18:
    ans = -1
print(ans)
    
    

### FIXED CODE ###

#import numpy as np
import math
n = int(input())
a= list(map(int,input().split()))
a.sort(reverse=1)

ans = a[0]

for i in range(1,n):
    if a[-1] == 0:
        print("0")
        exit()
    elif a[i] > 10**18:
        print("-1")
        exit()
    elif ans > 10**18:
        print("-1")
        exit()
    else:
        ans *= a[i]

if ans > 10**18:
    ans = -1
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
cities = ([list(map(int, input().split())) for _ in range(m)])
for city in cities:
    pref = str(city[0]).zfill(6)
    same_pref = sorted([i[1] for i in cities if i[0] == city[0]])
    rank = str(same_pref.index(city[1]) + 1).zfill(6)
    print(pref + rank)


### FIXED CODE ###

n, m = map(int, input().split())
# i は 通し番号
cities = sorted(([list(map(int, input().split())) + [i] for i in range(m)]))
pref = cities[0]
counter = 1
for city in cities:
    if pref != city[0]:
        counter = 1
    pref = city[0]
    rank = counter
    number = str(pref).zfill(6) + str(rank).zfill(6)
    city.append(number)
    counter += 1
for i in sorted(cities, key=lambda x: x[2]):
    print(i[3])
### BUGGY CODE ###

import sys
input=sys.stdin.readline
def main():
    n,s=map(int,input().split())
    MOD=998244353
    import numpy as np
    A=list(map(int,input().split()))
    dp=[np.array([0]*(n+1)) for _ in range(s)]
    dp=[np.array([1]+[0]*n)]+dp 
    for i in range(n):
        u=A[i]
        for j in range(s,-1,-1):
            if j+u<=s:
                dp[j+u][1:]+=dp[j][:-1]
                dp[j+u]%=MOD
    #print(dp)

    w=dp[s]
    q=[2**(n-i) for i in range(n+1)]
    ans=w*q%MOD
    print(ans.sum()%MOD)
#print(w)

main()

### FIXED CODE ###

mod = 998244353
N, S = map(int,input().split())
A = list(map(int,input().split()))
dp = [[0 for i in range(S+1)] for j in range(N+1)]
dp[0][0] = 1

for i in range(N):
    for j in range(S+1):
        dp[i+1][j] += dp[i][j] * 2
        if j + A[i] <= S:
            dp[i+1][j+A[i]] += dp[i][j]
        dp[i+1][j] %= mod

print(dp[N][S])