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

# 初期入力
#import numpy as np #消すの忘れてた
N,Q = (int(x) for x in input().split())
aa=0  
bb=0
a=[0] 
b=[0]
a_set =set()
#ki_kouzou =np.zeros((N+1,1),dtype=np.int32)
ki_kouzou_dic ={i:set() for i in range(1,N+1)}

#木の構造を入力
for i in range(1,N): #直接つながっているところ。
    aa,bb = (int(x) for x in input().split())
    if bb in a_set: #親子判定 頂点3⇒頂点2もありうる
        #np.append(ki_kouzou[bb,:],aa,axis=1)
        a_set.add(aa)
        ki_kouzou_dic[bb].add(aa)
    else:
        #np.append(ki_kouzou[aa,:],bb,axis=1)
        #ki_kouzou[aa].append(bb)
        ki_kouzou_dic[aa].add(bb)
        a_set.add(bb)
    a.append(aa)     
    b.append(bb)


#間接的に繋がっているところ
kansetu ={i:set() for i in range(1,N+1)}
for ki_key in range(1,N+1) :
    for v_v in ki_kouzou_dic[ki_key]:
        if v_v in ki_kouzou_dic.keys():
            kansetu[ki_key] = kansetu[ki_key] | ki_kouzou_dic[v_v] 

for i in range(1,N+1):
    ki_kouzou_dic[i] =ki_kouzou_dic[i] | kansetu[i] #直接 ＋ 間接
    ki_kouzou_dic[i].add(i) #各頂点自身はは必ずポイント加算あり


# ポイント入力-計算
point={i:0 for i in range(1,N+1)}
pp=0 ; xx=0
for _ in range(Q):
    pp,xx = (int(x) for x in input().split())
    for i in ki_kouzou_dic[pp]:
        point[i] += xx 

print(*point.values())

### FIXED CODE ###

from collections import OrderedDict
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
#初期データ、構造
N,Q = (int(x) for x in input().split())
connection ={i:set() for i in range(1,N+1)}
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b)
    connection[b].add(a)
#point =OrderedDict({i:0 for i in range(1,N+1)})
point ={i:0 for i in range(1,N+1)}
for i in range(Q):
    p,x = (int(x) for x in input().split())
    point[p] +=x

def DFS(now,prev = -1):
    for next in connection[now]:
        if next == prev:
            continue
        point[next] +=point[now] 
        DFS(next,now)

DFS(1)
print(*point.values())
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

n = int(input())

sum_ = 0
for a in range(1, n+1):
  for b in range(1, n+1):
    for c in range(1, n+1):
      sum_ += gcd(a, b, c)
    
print(sum_)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

n = int(input())

sum_ = 0
for a in range(1, n+1):
  for b in range(1, n+1):
    for c in range(1, n+1):
      sum_ += gcd(a, b, c)
    
print(sum_)
### BUGGY CODE ###

import sys

n, m, k = map(int, sys.stdin.readline().split())
ab = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]
cd = [tuple(map(int, sys.stdin.readline().split())) for _ in range(k)]
friend = [[] for _ in range(n+1)]
for a, b in ab:
    friend[a].append(b)
    friend[b].append(a)
block = [set() for _ in range(n+1)]
for c, d in cd:
    block[c].add(d)
    block[d].add(c)

root = list(range(n+1))
size = [1] * (n + 1)
height = [1] * (n + 1)

def find_root(u):
    v = root[u]
    if v == u:
        return u 
    w = find_root(v)
    root[u] = w 
    return w 

def unite(u, v):
    ru = find_root(u)
    rv = find_root(v)
    if ru != rv:
        if height[ru] >= height[rv]:
            root[rv] = ru 
            height[ru] = max(height[ru], height[rv] + 1)
            size[ru] += size[rv]
        else:
            root[ru] = rv 
            size[rv] += size[ru]

def main():
    for u in range(1, n+1):
        for v in friend[u]:
            unite(u, v)
    
    g = [set() for _ in range(n+1)]
    for i in range(1, n+1):
        g[find_root(i)].add(i)
    
    for i in range(1, n+1):
        yield len(g[root[i]] - block[i]) - len(friend[i]) - 1

if __name__ == '__main__':
    ans = main()
    print(*ans, sep=' ')

### FIXED CODE ###

import sys

n, m, k = map(int, sys.stdin.readline().split())
ab = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]
cd = [tuple(map(int, sys.stdin.readline().split())) for _ in range(k)]
friend = [[] for _ in range(n+1)]
for a, b in ab:
    friend[a].append(b)
    friend[b].append(a)
block = [[] for _ in range(n+1)]
for c, d in cd:
    block[c].append(d)
    block[d].append(c)

root = list(range(n+1))
size = [1] * (n + 1)
height = [1] * (n + 1)

def find_root(u):
    v = root[u]
    if v == u:
        return u 
    w = find_root(v)
    root[u] = w 
    return w 

def unite(u, v):
    ru = find_root(u)
    rv = find_root(v)
    if ru != rv:
        if height[ru] >= height[rv]:
            root[rv] = ru 
            height[ru] = max(height[ru], height[rv] + 1)
            size[ru] += size[rv]
        else:
            root[ru] = rv 
            size[rv] += size[ru]

def main():
    for u in range(1, n+1):
        for v in friend[u]:
            unite(u, v)

    for u in range(1, n+1):
        find_root(u)

    for u in range(1, n+1):
        ru = root[u]
        cnt = size[ru] - 1  - len(friend[u])
        for v in block[u]:
            if root[v] == ru:
                cnt -= 1
        yield cnt

if __name__ == '__main__':
    ans = main()
    print(*ans, sep=' ')
### BUGGY CODE ###

from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    for i in range(len_S):
        for j in range(i+3,len_S):
            if j == i+3:
                mod = int(S[len_S-j-1:len_S-i])%3
            else:
                mod = (mod+int(S[len_S-j-1]))%3
            if mod == 0:
                _ = int(S[len_S-j-1:len_S-i])
                if _%673==0:
                    cnt += 1
                    break
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


### FIXED CODE ###

from sys import stdin


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    for i in range(len_S):
        for j in range(i+3,len_S):
            if j == i+3:
                mod = int(S[len_S-j-1:len_S-i])%3
            else:
                mod = (mod+int(S[len_S-j-1]))%3
            if mod == 0:
                _ = int(S[len_S-j-1:len_S-i])
                if _%673==0:
                    cnt += 1
                    break
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


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

    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 0
    mod_arr = [0] * 2019
    mod_arr[0] += 1

    num, dec = 0, 1
    for s in S[::-1]:
        num += int(s)*dec
        num %= 2019
        dec *= 10
        dec %= 2019
        mod_arr[num] += 1

    for i in range(2019):
        if mod_arr[i] > 0:
            cnt += mod_arr[i]*(mod_arr[i]-1)//2
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)
### BUGGY CODE ###

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

if L <= 2019 and 2019 <= R:
    ans = 0

else:
    ans = 2019
    for i in range(L, R):
        for j in range(L+1, R+1):
#             print(i, j)
            tmp = (i*j) % 2019
            if tmp <= ans:
                ans = tmp
                if ans == 0:
                    break

print(ans)

### FIXED CODE ###

import sys

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

if L <= 2019 and 2019 <= R:
    ans = 0

else:
    ans = 2019
    for i in range(L, R):
        for j in range(L+1, R+1):
            if (i % 2019 == 0) or (j % 2019 == 0):
                ans = 0
                print(ans)
                sys.exit()
            tmp = (i*j) % 2019
            if tmp <= ans:
                ans = tmp
print(ans)
### BUGGY CODE ###

# N, K = 5, 3
# HRR = [10, 30, 40, 50, 20]

N, K = 3, 1
HRR = [10, 20, 10]


N,K = 2, 100
HRR = [10, 10]

N,K = 10, 4
HRR = [40, 10, 20, 70, 80, 10, 20, 70, 80, 60]

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


def calculate(n, k, hrr):
    result = []
    for i in range(n):
        if i == 0:
            result.append(0)
            continue
        srr = []
        for j in range(1, k + 1):
            index = i - j
            if index >= 0:
                srr.append(result[index] + abs(hrr[i] - hrr[index]))
        result.append(min(srr))

    print(result[-1])


calculate(N, K, HRR)


### FIXED CODE ###

# N, K = 5, 3
# HRR = [10, 30, 40, 50, 20]

N, K = 3, 1
HRR = [10, 20, 10]

N, K = 2, 100
HRR = [10, 10]

N, K = 10, 4
HRR = [40, 10, 20, 70, 80, 10, 20, 70, 80, 60]

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


def calculate(n, k, hrr):
    result = []
    for i in range(n):
        if i == 0:
            result.append(0)
            continue

        mins = -1
        for j in range(1, k + 1):
            index = i - j
            if index >= 0:
                value = result[index] + abs(hrr[i] - hrr[index])
                if mins == -1:
                    mins = value
                else:
                    if value < mins:
                        mins = value
        result.append(mins)

    print(result[-1])


calculate(N, K, HRR)
### BUGGY CODE ###

def main():
 
  import sys
  
  def input():
    return(sys.stdin.readline()[:-1])
  
  import collections
 
  N = int(input())
  S = list(input())
 
  CNT_S = collections.Counter(S)
 
  cnt_r = CNT_S['R']
  cnt_b = CNT_S['B']
  cnt_g = CNT_S['G']
 
  total = cnt_r * cnt_g * cnt_b
  subdu = 0
 
 
  for pos in range(N):
      for i in range(1, N):
 
          index_r = pos
          index_m = pos + i
          index_l = pos + 2 * i
 
          if (index_l < N and index_m < N and index_r < N):
              if (S[index_l] != S[index_m] and S[index_l] != S[index_r] and S[index_m] != S[index_r]):
                  subdu += 1
 
 
  ans = total - subdu
 
  print(ans)
  
if __name__ == '__main__':
    main()

### FIXED CODE ###

import collections

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

CNT_S = collections.Counter(S)

cnt_r = CNT_S['R']
cnt_b = CNT_S['B']
cnt_g = CNT_S['G']

total = cnt_r * cnt_g * cnt_b
subdu = 0


for pos in range(N):
    for i in range(1, N):
    
        index_r = pos
        index_m = pos + i
        index_l = pos + 2 * i
        
        if (index_l < N and index_m < N and index_r < N):
            if (S[index_l] != S[index_m] and S[index_l] != S[index_r] and S[index_m] != S[index_r]):
                subdu += 1


ans = total - subdu

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

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = sorted(list(map(int, input().split())), reverse = True)

list = []
for i in range(x):
    for j in range(y):
        list.append(a[i]+b[j])
list.sort(reverse = True)
list1 = []
for i in range(min(k,x*y)):
    for j in range(y):
        list1.append(list[i]+c[j])
list1.sort(reverse = True)
for i in range(k):
    print(list1[i])

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse = True)
b = sorted(list(map(int, input().split())), reverse = True)
c = sorted(list(map(int, input().split())), reverse = True)

list = []
for aa in a:
    for bb in b:
        list.append(aa+bb)
list.sort(reverse = True)
list = list[:k]

list1 = []
for ab in list:
    for cc in c:
        list1.append(ab+cc)
list1.sort(reverse = True)
list1 = list1[:k]

for i in range(k):
    print(list1[i])
### BUGGY CODE ###

def myPow(x, n):
  if n == 0:
    return 1

  K = 1
  while n > 1:
    if n % 2 != 0:
      K *= x

    x *= x
    n //= 2

  return K * x



N = int(input())
strX = input()

#10進数に変換
decX = int(strX,2)

#1の数をカウント
pop_c = strX.count('1')

# X % popcount+1
f_p = decX % (pop_c + 1)

# X % popcount-1(0になる時は0)
if pop_c == 1:
  f_m = 0
else:
  f_m = decX % (pop_c - 1)

for i in range(0,N):
  if strX[i] == '0':
    exp = myPow(2,(N-1-i))
    pop_a = (f_p + (exp % (pop_c + 1))) % (pop_c + 1) 
    Ans = 1
    
  elif strX[i] == '1' and pop_c == 1:
    pop_a = 0
    Ans = 0
    
  else:
    exp = myPow(2,(N-1-i))
    pop_a = f_m - (exp % (pop_c - 1))
    if pop_a < 0:
      pop_a = pop_a + pop_c - 1
    Ans = 1
  
  while pop_a > 0:
    wkpop = bin(pop_a).count('1')
    pop_a = pop_a % wkpop
    Ans += 1
  
  print(Ans)

### FIXED CODE ###

N = int(input())
strX = input()

#10進数に変換
decX = int(strX,2)

#1の数をカウント
pop_c = strX.count('1')

# X % popcount+1
f_p = decX % (pop_c + 1)

# X % popcount-1(0になる時は0)
if pop_c == 1:
  f_m = 0
else:
  f_m = decX % (pop_c - 1)

for i in range(0,N):
  if strX[i] == '0':
    pop_a = (f_p + pow(2,(N-1-i),(pop_c + 1))) % (pop_c + 1) 
    Ans = 1
    
  elif pop_c == 1:
    pop_a = 0
    Ans = 0
    
  else:
    pop_a = f_m - (pow(2,(N-1-i),(pop_c - 1)))
    if pop_a < 0:
      pop_a = pop_a + pop_c - 1
    Ans = 1
  
  while pop_a > 0:
    wkpop = bin(pop_a).count('1')
    pop_a = pop_a % wkpop
    Ans += 1
  
  print(Ans)
### BUGGY CODE ###

s = list(input())
s.reverse()
n = len(s)
now = 0
mods = [0] * 2019
for i in range(n):
    now += (10 ** i) * int(s[i])
    mods[now % 2019] += 1
ans = mods[0]
for i in mods:
    ans += (i * (i - 1)) // 2
print(ans)


### FIXED CODE ###

if __name__ == '__main__':

    s = list(input())
    s.reverse()
    n = len(s)
    now = 0
    mods = [0] * 2019
    mods[0] += 1
    ten = 1
    for i in range(n):
        now += ten * int(s[i])
        now %= 2019
        ten *= 10
        ten %= 2019
        mods[now] += 1
    ans = 0
    for i in mods:
        ans += (i * (i - 1)) // 2
    print(ans)
### BUGGY CODE ###

H, W, M = map(int, input().split())
bom = [list(map(int, input().split())) for _ in range(M)]

hBom = [0]*H
wBom = [0]*W

# 各行、各列の爆破対象をカウント
for h, w in bom:
    hBom[h-1] += 1
    wBom[w-1] += 1

# 爆破対象の最大数と最大になる行と列の番号を調べる
maxHBom = max(hBom)
maxWBom = max(wBom)
maxHBomIndex = [index for index, h in enumerate(hBom) if h == maxHBom]
maxWBomIndex = [index for index, w in enumerate(wBom) if w == maxWBom]

# 爆破対象が最大になる行と列の組み合わせについて、
# 爆弾を配置する場所が爆破対象であるかないかで場合分け
for h in maxHBomIndex:
    for w in maxWBomIndex:
        if [h+1, w+1] not in bom:
            print(hBom[h] + wBom[w])
            exit()
else:
    print(hBom[h] + wBom[w] - 1)


### FIXED CODE ###

H, W, M = map(int, input().split())
boms = [tuple(map(int, input().split())) for _ in range(M)]
# boms = [list(map(int, input().split())) for _ in range(M)]

hBom = [0]*H
wBom = [0]*W

# 各行、各列の爆破対象をカウント
for h, w in boms:
    hBom[h-1] += 1
    wBom[w-1] += 1

# 爆破対象の最大数と最大になる行と列の番号を調べる
maxHBom = max(hBom)
maxWBom = max(wBom)
maxHBomIndex = [index for index, h in enumerate(hBom) if h == maxHBom]
maxWBomIndex = [index for index, w in enumerate(wBom) if w == maxWBom]

# 爆破対象が最大になる行と列の組み合わせについて、
# 爆弾を配置する場所が爆破対象であるかないかで場合分け
boms = set(boms)
for h in maxHBomIndex:
    for w in maxWBomIndex:
        if (h+1, w+1) not in boms:
            print(maxHBom + maxWBom)
            exit()
else:
    print(maxHBom + maxWBom - 1)
### BUGGY CODE ###

def main():
    x, n = map(int, input().split())
    p_lst = list(map(int, input().split()))

    if n == 0:
        minimum = x
    else:
        if x not in p_lst:
            minimum = x

        else:
            lst = []
            flag = False

            while True:
                x1 = x
                x2 = x
                x1 += 1
                x2 -= 1

                if x1 not in p_lst:
                    lst.append(x1)
                    flag = True
                if x2 not in p_lst:
                    lst.append(x2)
                    flag = True

                if flag:
                    break

            minimum = min(lst)

    print(minimum)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    x, n = map(int, input().split())
    p_lst = list(map(int, input().split()))

    if n == 0:
        minimum = x
    else:
        if x not in p_lst:
            minimum = x

        else:
            lst = []
            flag = False
            x1 = x
            x2 = x

            while True:
                x1 += 1
                x2 -= 1

                if x1 not in p_lst:
                    lst.append(x1)
                    flag = True
                if x2 not in p_lst:
                    lst.append(x2)
                    flag = True

                if flag:
                    break

            minimum = min(lst)

    print(minimum)


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

N, M = map(int, input().split())
A, B = [], []
g = {}
for i in range(1, N+1):
    g[i] = []
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
    g[a].append(b)
    g[b].append(a)


def dfs(graph, start):
    visited = []
    stack = []
    stack.append(start)
    result = []
    while len(stack) > 0:
        next = stack.pop()
        if next in visited:
            continue
        result.append(next)
        visited.append(next)
        for nei in graph[next]:
            stack.append(nei)
    return result


def wfs(graph, start):
    visited = []
    queue = []
    queue.append(start)
    result = []
    while len(queue) > 0:
        next_city = queue.pop(0)
        if next_city in visited:
            continue
        result.append(next_city)
        visited.append(next_city)
        for nei in graph[next_city]:
            queue.append(nei)
    return result


for i in range(M):
    ans = 0
    g[A[i]].remove(B[i])
    g[B[i]].remove(A[i])
    for j in range(1, N+1):
        # print(wfs(g, j))
        for k in range(j, N+1):
            if k not in wfs(g, j):
                ans += 1
    print(ans)


### FIXED CODE ###

class UnionFind():
    # 初期化
    # 全てのノードの親は -1 とする
    def __init__(self, n):
        self.par = [-1] * n

    # xがどのグループに属しているか調べる
    def root(self, x):
        # xが親のとき
        if self.par[x] < 0:
            return x
        # xの親がさらに親をもつとき、それをxの親とする
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    # 自分のいるグループの頂点数を調べる
    def size(self, x):
        return -self.par[self.root(x)]

    # xとyをくっつける
    def connect(self, x, y):
        x = self.root(x)
        y = self.root(y)
        # すでにくっついていたらくっつけない
        if x == y:
            return

        # 大きい方(x)に小さい方(y)をくっつける
        if self.size(x) < self.size(y):
            x, y = y, x

        # xのサイズを更新
        self.par[x] += self.par[y]
        # yの親をxに変更
        self.par[y] = x

        return


N, M = map(int, input().split())
A, B = [], []
for _ in range(M):
    a, b = map(int, input().split())
    # インデックスをずらす
    A.append(a-1)
    B.append(b-1)

uni = UnionFind(N)

ans = [N * (N-1) // 2]
for i in range(M-1, 0, -1):
    ans.append(ans[-1])
    # 繋がっていないグループがつながったとき
    if uni.root(A[i]) != uni.root(B[i]):
        ans[-1] -= uni.size(A[i]) * uni.size(B[i])
        uni.connect(A[i], B[i])

for item in reversed(ans):
    print(item)
### BUGGY CODE ###

def main():
    n, k, c = map(int, input().split())
    s = input()

    if c == 0:
        if s.count('o') == k:
            ret = [i for i, c in enumerate(s) if c == 'o']
        else:
            ret = []

    else:

        go = set()
        back = set()

        i = 0
        while i < n:
            if s[i] == 'o':
                go.add(i)
                if len(go) == k:
                    break
                i += c + 1
            else:
                i += 1

        if len(go) < k:
            return

        i = n - 1
        while i >= 0:
            if s[i] == 'o':
                back.add(i)
                if len(back) == k:
                    break
                i -= c + 1
            else:
                i -= 1

        if len(back) < k:
            return

        isec = go & back

        ret = []
        for elm in isec:
            go = set()
            i = 0
            while i < n:
                if i == elm:
                    i += 1
                    continue

                if s[i] == 'o':
                    go.add(i)
                    if len(go) == k:
                        break
                    i += c + 1
                else:
                    i += 1

            if len(go) < k:
                ret.append(elm)

    print(*map(lambda x: x + 1, ret), sep='\n')


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, K, C = map(int, input().split())
    s = input()

    L = [-1] * K
    R = [-1] * K

    i = 0
    cur = 0
    while i < N and cur < K:
        if s[i] == 'o':
            L[cur] = i
            cur += 1
            i += C + 1
        else:
            i += 1

    i = N - 1
    cur = K - 1
    while i >= 0 and cur >= 0:
        if s[i] == 'o':
            R[cur] = i
            cur -= 1
            i -= C + 1
        else:
            i -= 1

    ans = (left + 1 for left, right in zip(L, R) if left == right)

    print(*ans, sep='\n')


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

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
dp = [0 for _ in range(N+1)]
MOD = int(1e9) + 7
dp[0] = 1
# DP
if 1 not in a:
    dp[1] = 1
for i in range(2, N+1):
    if i not in a:
        dp[i] = (dp[i-1] + dp[i-2]) % MOD
    else:
        dp[i] = 0
print(dp[-1])

### FIXED CODE ###

import sys

n, m = map(int, input().split())
aaa = set()
if m != 0:
    for _ in range(m):
        aaa.add(int(input()))
    
    
dp = [0] * (n + 1) # 0 array
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0 # 入ってはいけない段に1が存在した場合は0
MOD = int(1e9) + 7

for i in range(2, n + 1):
    if i in aaa:
        continue
    dp[i] = (dp[i-2] + dp[i-1]) % MOD # 入ってはいけないところからの遷移の場合0を加算
print(dp[n])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    n, s = map(int, input().split())
    a = list(map(int, input().split()))

    dp = [0]*(s+1)
    dp[0] = 1
    mod = 998244353

    for i in range(n):
        for j in range(s, -1, -1):
            if dp[j] and j + a[i] <= s:
                dp[j+a[i]] += dp[j]
                dp[j+a[i]] %= mod
            dp[j] *= 2
            dp[j] %= mod

    print(dp[s])
    
    
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
  n, s = map(int, input().split())
  a = [int(x) for x in input().split()]
  mod = 998244353
  
  dp = [[0]*(s+1) for _ in range(n+1)]
  dp[0][0] = 1
  for i in range(1, n+1):
    for j in range(s, -1, -1):
      dp[i][j] += dp[i-1][j]*2
      dp[i][j] %= mod
      if dp[i-1][j] and j+a[i-1] <= s:
        dp[i][j+a[i-1]] += dp[i-1][j]
        dp[i][j+a[i-1]] %= mod

  print(dp[n][s])
  
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

from collections import defaultdict

N, T = map(int, input().split())
A = [int(x) for x in input().split()]

c = defaultdict(int)
for i in range(N - 1):
    x = max(A[i + 1:])
    c[x - A[i]] += 1
print(c[max(c)])


### FIXED CODE ###

from collections import defaultdict

N, T = map(int, input().split())
A = [int(x) for x in input().split()]

B = [0] * N
for i in range(N - 1):
    a = A[N - i - 1]
    B[i + 1] = max(B[i], a)
B = B[::-1]

c = defaultdict(int)
for i in range(N - 1):
    c[B[i] - A[i]] += 1
print(c[max(c)])
### BUGGY CODE ###

n = int(input())
aaa = list(map(int, input().split()))
dp = [[0] * (n + 1) for _ in range(n)]
for i, a in enumerate(aaa):
    dp[i][i + 1] = (a, 0)
for w in range(2, n + 1):
    for l in range(n - w + 1):
        r = l + w
        # take left
        dpl, dpr = dp[l + 1][r]
        tl_x = aaa[l] + dpr
        tl_y = dpl
        tl_score = tl_x - tl_y
        # take_right
        dpl, dpr = dp[l][r - 1]
        tr_x = aaa[r - 1] + dpr
        tr_y = dpl
        tr_score = tr_x - tr_y
        if tl_score > tr_score:
            dp[l][r] = (tl_x, tl_y)
        else:
            dp[l][r] = (tr_x, tr_y)
print(dp[0][n][0] - dp[0][n][1])


### FIXED CODE ###

n = int(input())
aaa = list(map(int, input().split()))
dp = [[0] * (n + 1) for _ in range(n + 1)]
for w in range(1, n + 1):
    for l in range(n - w + 1):
        r = l + w
        dpl = -dp[l + 1][r] + aaa[l]
        dpr = -dp[l][r - 1] + aaa[r - 1]
        dp[l][r] = max(dpl, dpr)
print(dp[0][n])