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

N, K= map(int,input().split())
A = list(map(int,input().split()))
p=0
while p<K:
  B=[0]*(N+1)
  for i in range(N):
    l = max(i-A[i],0)
    r = min(i+A[i]+1,N)
    B[l] +=1
    B[r] -=1
  for i in range(N):
    A[i] = sum(B[0:i+1])
  p +=1        
  if min(A)==N:
    break
print(*A)

### FIXED CODE ###

N, K= map(int,input().split())
A = list(map(int,input().split()))
a=A[:]
for _ in range(K):
  B=[0]*(N+1)
  for i in range(N):
    t = a[i]
    B[max(i-t,0)] +=1
    B[min(i+t+1,N)] -=1
  for i in range(N):
    B[i+1] += B[i]
  a=B[:N]        
  if min(a)==N:
    break
print(*a)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

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

MOD = 10 ** 9 + 7

if m == 1:
    print('1')
    exit()

factor = []
temp = 0
x = 2
while m > 1:
    if m % x == 0:
        m //= x
        temp += 1
    elif temp > 0:
        factor.append(temp)
        temp = 0
        x += 1
    else:
        x += 1
factor.append(temp)

nCr = {}
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n;
    if (n, r) in nCr: return nCr[(n, r)]

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p;
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    nCr[(n, r)] = result
    return result;

ans = 1
for x in factor:
    ans *= cmb(x + n - 1, n - 1)
    ans %= MOD

print(ans)

### FIXED CODE ###

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

MOD = 10 ** 9 + 7

if m == 1:
    print('1')
    exit()

factor = []
temp = 0
x = 2
while m > 1:
    if m % x == 0:
        m //= x
        temp += 1
    elif temp > 0:
        factor.append(temp)
        temp = 0
        x += 1
    else:
        x += 1
factor.append(temp)

nCr = {}
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n;
    if (n, r) in nCr: return nCr[(n, r)]

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p;
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    nCr[(n, r)] = result
    return result;

ans = 1
for x in factor:
    ans *= cmb(x + n - 1, n - 1)
    ans %= MOD

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

import math
K = int(input())
S = 0
for a in range(K):
    for b in range(K):
        for c in range(K):
            S += math.gcd(math.gcd(a+1,b+1),c+1)
print(S)

### FIXED CODE ###

import math
 
 
N = int(input())
 
s = 0
 
for i in range(N):
    for j in range(N):
        ss = math.gcd(i+1,j+1)
        for k in range(N):
            s +=math.gcd(ss,k+1)
 
print(s)
### BUGGY CODE ###

import heapq
N,M = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(N)]
l = sorted(l)
heap = []
a = 0
b = 0
for i in range(1,M+1):
    while l[a][0] <= i:
        a = 0
        heapq.heappush(heap,-(l[a][1]))
        a += 1
    if heap == []:
        continue
    else:
        b += -(heapq.heappop(heap))
print(b)






### FIXED CODE ###

import heapq
N,M = map(int,input().split())
l = [tuple(map(int,input().split())) for _ in range(N)]
l = sorted(l,reverse=True)
heap = []
ans = 0
for i in range(1,M+1):
        while l and l[-1][0] == i:
            heapq.heappush(heap, (l.pop()[1]*(-1)))
        if heap :
            ans -= (heapq.heappop(heap))
print(ans)
### BUGGY CODE ###

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

dp = [0]*N
dp[1] = abs(l[0]-l[1])

for i in range(2,N):
  num = int(10e10)
  for j in range(1,K+1):
    if i-j < 0:
      dp[i] = num
      break
    else:
      tmp = dp[i-j]+abs(l[i]-l[i-j])
      num = min(tmp,num)
  dp[i] = num

print(dp[N-1])


### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,K = IL()
l = np.array(IL())

dp = np.zeros(N,dtype=int)
dp[0] = 0

for i in range(1,N):
    if i-K < 0:
        dp[i] = np.min(dp[:i]+np.abs(l[i]-l[:i]))
    elif i-K >= 0:
        dp[i] = np.min(dp[i-K:i]+np.abs(l[i]-l[i-K:i]))

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

import sys
import math
import fractions
import bisect
import queue
import heapq
import collections
import itertools
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint=====================================
N, K = map(int, input().split())
N, M = map(int, input().split())
A, B = map(int, input().split())

H, W = map(int, input().split())

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

1行のstring=================================
S, T = input().split()

1行の整数配列================================
P = list(map(int,input().split()))

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
D = list(map(int,input().split()))

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

T = list(map(int,input().split()))

改行あり整数==================================
X = []
Y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    X.append(x1)
    Y.append(y1)

A = []
for i in range(N):
    a=int(input())
    A.append(a)

Pair = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    Pair.append((x1, y1))
    
2次元整数配列=====================================
A = []
for i in range(N):
    tmp = list(map(int,input().split()))
    A.append(tmp)


N行M列の初期化====================================
dp = [[VAL] * RETU for i in range(GYO)]

'''

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

common1 = 1
for a in A[:len(A)// 2]:
    common1 = common1 * a // math.gcd(common1, a)


common2 = 1
for a in A[len(A)// 2:]:
    common2 = common2 * a // math.gcd(common2, a)

common = common1 * common2 // math.gcd(common1, common2)

ans = 0
for a in A:
    ans += common // a
    ans %= MOD

print(ans)




### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)
import math




N = int(input())


import fractions
a = list(map(int, input().split()))
koubai = a[0]
small = []
for i in range(0, N//2):
    small.append(a[2*i + 1] * a[2*i] // fractions.gcd(a[2*i + 1], a[2*i]))

small.append(a[-1])
for i in range(len(small)):
    koubai = koubai * small[i] // fractions.gcd(koubai, small[i])


ans = int(0)
for i in range(N):
    ans += koubai // a[i]
    
ans %= 1000000007

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

# https://atcoder.jp/contests/abc145/tasks/abc145_d
import math
X, Y = list(map(int, input().split()))

if (X + Y) % 3 != 0:
    print(0)
    exit()


n = int((2*X - Y) // 3)
m = int((2*Y - X) // 3)

if n < 0 or m < 0:
    print(0)
    exit()

MOD = 10 ** 9 + 7
result = math.factorial(n + m) * pow(math.factorial(n), -1,
                                     MOD) * pow(math.factorial(m), -1, MOD) % MOD
print(result)


### FIXED CODE ###

# https://atcoder.jp/contests/abc145/tasks/abc145_d
import math
X, Y = list(map(int, input().split()))

if (X + Y) % 3 != 0:
    print(0)
    exit()


n = int((2*X - Y) // 3)
m = int((2*Y - X) // 3)

if n < 0 or m < 0:
    print(0)
    exit()


def comb(n, k):
    c = 1
    for i in range(k):
        c *= n - i
        c %= MOD
    d = 1
    for i in range(1, k + 1):
        d *= i
        d %= MOD
    return (c * pow(d, MOD - 2, MOD)) % MOD

MOD = 10 ** 9 + 7
result = comb(n+m, n)
print(result)
### BUGGY CODE ###

import math

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

C = list(set(A))
M = len(C)
t = []
t1 = []
t2 = []
for i in range(M):
  t.append(A.count(C[i]))
  temp = A.count(C[i])
  if temp >=3:
    t1.append(math.factorial(temp-1)/(math.factorial(temp-3)*2))
    t2.append(math.factorial(temp)/(math.factorial(temp-2)*2))    
  elif temp == 2:
    t1.append(0)
    t2.append(math.factorial(temp)/(math.factorial(temp-2)*2))
  else:
    t1.append(0)
    t2.append(0)

#print(t,t1,t2)


s = []  
for i in range(M):
  ans = 0
  for j in range(M):
    if i == j:
      ans += t1[j]
    else:
      ans += t2[j]
  s.append(int(ans))

jisyo = dict(zip(C,s))
#print(jisyo[1])
for i in range(N):
  print(jisyo[A[i]])

### FIXED CODE ###

import math

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

C = list(set(A))
M = len(C)
t = []
anst = 0
dic = {}
for i in A:
  if not i in dic:
    dic[i] = 0
  dic[i] += 1

jisyo = {}
for i in range(M):
  temp = dic[C[i]]
  jisyo[C[i]] = temp
  #t.append(A.count(C[i]))
  if temp >=2:
    anst += temp*(temp-1)/2

#jisyo = dict(zip(C, t))
#print(jisyo)   
for i in range(N):
  #print(t[C.index(A[i])])
  print(int(anst-jisyo[A[i]]+1))
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
out = [0] * n
for i in range(n):
    out[i] = (str(a.index(n-i)+1))
print(' '.join(out[::-1]))


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
out = [0] * n
for i in range(len(a)): out[a[i] - 1] = i + 1
print(' '.join([str(i) for i in out]))
### BUGGY CODE ###

import numpy as np
n,k = list(map(int,input().split()))
p = np.array(list(map(int,input().split())))

P = [p[i:i+k].sum() for i in range(n-k+1)]
mp = p[np.argmax(P):np.argmax(P)+k]

ans = 0
for i in mp:
  j = i//2
  if i%2 == 0:
    ans += ((i+1)*j)/i
  else:
    ans += ((i+1)*j + j + 1)/i

print(ans)


### FIXED CODE ###

from itertools import accumulate
n,k = list(map(int,input().split()))
p = list(map(int,input().split()))

P = list(accumulate([(i+1)/2 for i in p]))
P = [0] + P
ans = max([P[i+k]-P[i] for i in range(n-k+1)])
print(ans)
### BUGGY CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

n = int(input())
a = list(map(int, input().split()))
b = []
lst = [0] * n
for i, x in reversed(list(enumerate(a))):
  if lst[i] % 2 != x:
    for y in make_divisors(i+1):
      lst[y-1] += 1
    b.append(i+1)
print(len(b))
if len(b) > 0:
  print(*reversed(b))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = []
lst = [0] * n
for i, x in reversed(list(enumerate(a))):
  if sum(lst[i::i+1]) % 2 != x:
    lst[i] += 1
    b.append(i+1)
print(len(b))
if len(b) > 0:
  print(*reversed(b))
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
d2 = deque()
ans = 0
s = set() # いったところ
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2, -1, 0, 1, 2]

while True:
  # 移動A
  while len(d) != 0:
    Th, Tw = d.popleft()
    s.add((Th, Tw))
    d2.append((Th,Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if not _p in s and 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and (not (_p) in d):
        d.append(_p)
  # 移動B
  ans += 1
  while len(d2) != 0:
    Th, Tw = d2.popleft()
    for i in b:
      for j in b:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if not _p in s and 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.':
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()
### BUGGY CODE ###

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

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

print(ans)

### FIXED CODE ###

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

ans = 0
for x in range(K+1):
  for y in range(min(S-x, K)+1):
    if S-x-y <= K: ans += 1
    
print(ans)
### BUGGY CODE ###

s = list(input())
q = int(input())

for i in range(q):
  query = input()
  if query[0] == '1':
    s.reverse()
  else:
    t, f, c = query.split()
    if f == '1':
      s.insert(0,c)
    else:
      s.append(c)

print(''.join(s))

### FIXED CODE ###

s = input()
q = int(input())

start = ''
end = ''

rvs = False

for i in range(q):
  query = input()
  if query[0] == '1':
    if rvs == False:
      rvs = True
    else:
      rvs = False
  else:
    t, f, c = query.split()
    if f == '1':
      if rvs == False:
        start = c + start
      else:
        end = end + c
    else:
      if rvs == False:
        end = end + c
      else:
        start = c + start

if rvs == False:
  print(start + s + end)
else:
  ans = start + s + end
  print(ans[::-1])
### BUGGY CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools

s = stdin.readline().rstrip()
n = int(stdin.readline().rstrip())

flag = 0
for i in range(n):
    q = [x for x in stdin.readline().rstrip().split()]

    if len(q) == 1:
        flag = (flag + 1) % 2
    else:
        if (q[1] == "1" and flag == 0) or (q[1] == "2" and flag == 1):
            s = q[2] + s
        else:
            s = s + q[2]

if flag == 1: s = ''.join(list(reversed(s)))
print (s)


### FIXED CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque

s = deque(stdin.readline().rstrip())
n = int(stdin.readline().rstrip())

flag = 0

for i in range(n):
    q = [x for x in stdin.readline().rstrip().split()]

    if len(q) == 1:
        flag = 1 - flag
    else:
        if (q[1] == "1" and flag == 0) or (q[1] == "2" and flag == 1):
            s.appendleft(q[2])
        else:
            s.append(q[2])

if flag == 1:
    s = ''.join(s)[::-1]
else:
    s = ''.join(s)
print (s)
### BUGGY CODE ###

input()

A = list(map(int, input().split()))
ans = 0

while all(a % 2 == 0 for a in A):
    A = [a % 2 for a in A]
    ans += 1

print(ans)

### FIXED CODE ###

input()

A = list(map(int, input().split()))
ans = 0

while all(a % 2 == 0 for a in A):
    A = [a / 2 for a in A]
    ans += 1

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

list = input().split()
l = int(list[0])
r = int(list[1])
# print(l, r)
 
min = (l*(l+1))%2019
for i in range(l,r):
  for j in range(i+1,r+1):
    k = (i*j)%2019
    # print(i,j,k)
    if k < min:
      min = k
print(min)

### FIXED CODE ###

list = input().split()
l = int(list[0])
r = int(list[1])
# print(l, r)
ans=2018
if r-l > 2019:
	min = 2019
else:
  min = r-l
for i in range(l,l+min):
  for j in range(l+1,l+min+1):
    if (i*j)%2019 < ans:
      ans = (i*j)%2019
      
print(ans)
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
ans = 0

for i in range(n):
  count = 0
  for j in range(i+1):
    if p[i] <= p[j]:
      count += 1
  if count == i+1:
    ans += 1
    
print(ans)
  

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
ans = 0
m= 10**10

for i in range(n):
  tmp = m
  m = min(m,p[i])
  if tmp != m:
    ans += 1
    
print(ans)
### BUGGY CODE ###

#問題文に連結と書いてあるのでどの部屋も互いに行き来できる
#自分がきたところを記録する幅優先探索をすればいい
n,m=list(map(int,input().split()))
#道を二次元リストで表す
road=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
  a,b=list(map(int,input().split()))
  road[a-1][b-1]=1
  road[b-1][a-1]=1
#幅優先探索
from collections import deque
q=deque([1])
ans=[0 for i in range(n)]
check=[0 for i in range(n)]
check[0]=1
while len(q)>0: 
  p=q.popleft()
  for j in range(n):
    if road[p-1][j]!=0 and check[j]==0:
      q.append(j+1)
      check[j]=1
      ans[j]=p
print("Yes")
for i in range(1,n):
  print(ans[i])
  

  

### FIXED CODE ###

n,m=list(map(int,input().split()))
road_input=[]
for i in range(m):
    road_input.append(list(map(int,input().split())))

#隣接リスト
road=[[] for i in range(n+1)]
for i in range(m):
    road[road_input[i][0]].append(road_input[i][1])
    road[road_input[i][1]].append(road_input[i][0])

from collections import deque
q=deque([1])
ans=[-1 for i in range(n)]
while len(q)>0:
  p=q.popleft()
  for i in road[p]:
    if ans[i-1]== -1:
      ans[i-1]=p
      q.append(i)

print("Yes")
for j in range(1,n):
    print(ans[j])
### BUGGY CODE ###

N=int(input())
A = [list(map(lambda x:int(x)-1,input().split())) for _ in [0]*N]

V = {(i,j):0 for i in range(N) for j in range(i+1,N)}
Ef = {(i,j):[] for i in range(N) for j in range(i+1,N)}
for i,B in enumerate(A):
    for a0,a1 in zip(B[:-1],B[1:]):
        k0 = tuple(sorted((i,a0)))
        k1 = tuple(sorted((i,a1)))
        Ef[k0].append(k1)
        V[k1] += 1

q = [k for k in V if V[k] == 0]
ans = 0
rmv = 0
while q:
    qq = []
    for k in q:
        for k2 in Ef[k]:
            V[k2] -= 1
            rmv += 1
            if V[k2] == 0 : qq.append(k2)
    ans += 1
    q = qq
if rmv != N*(N-2) : ans = -1
print(ans)

### FIXED CODE ###

#"""
import sys
input = sys.stdin.readline
#"""
def main():
    def get_key(i,j):
        if i<j: i,j = j,i
        return i*N+j
    N=int(input())
    A = [list(map(int,input().split())) for _ in [0]*N]
    V = [-1]*(N*N)
    for i in range(N):
        for j in range(i+1,N):
            V[get_key(i,j)] = 0
    Ef = [[] for _ in V]

    for i,B in enumerate(A):
        a0 = B[0]-1
        k1 = (i,a0)
        for a1 in B[1:]:
            a1 -= 1
            k0 = k1
            k1 = (i,a1)
            Ef[get_key(*k0)].append(get_key(*k1))
            V[get_key(*k1)] += 1

    q = [i for i,v in enumerate(V) if v == 0]
    ans = 0
    rmv = 0
    while q:
        qq = []
        for i in q:
            for j in Ef[i]:
                V[j] -= 1
                rmv += 1
                if V[j] == 0 : qq.append(j)
        ans += 1
        q = qq
    if rmv != N*(N-2) : ans = -1
    print(ans)
main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
MOD = 10**9+7
N = int(input())
edge = [[] for _ in range(N+1)]
dp = [[0]*2 for i in range(100005)]
# dp[v][c]: 頂点vを色cの根とする部分木の塗り分け方の総数
# 葉が決まると順々に求まっていく
for i in range(N-1):
    x,y = map(int,input().split())
    edge[x].append(y)
    edge[y].append(x)

# 0:white,1:black
def dfs(v,last=-1):
    dp[v][0] = 1
    dp[v][1] = 1
    for nv in edge[v]:
        if nv == last:
            continue
        dfs(nv, v)
        dp[v][0] = dp[v][0] * ((dp[nv][0] + dp[nv][1]) % MOD) % MOD
        dp[v][1] = dp[v][1] * dp[nv][0] % MOD


dfs(1)
print((dp[1][0] + dp[1][1])%MOD)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def main():
  MOD = 10**9+7
  N = int(input())
  edge = [[] for _ in range(N+1)]
  dp = [[0]*2 for i in range(100005)]
  # dp[v][c]: 頂点vを色cの根とする部分木の塗り分け方の総数
  # 葉が決まると順々に求まっていく
  for i in range(N-1):
      x,y = map(int,input().split())
      edge[x].append(y)
      edge[y].append(x)

  # 0:white,1:black
  def dfs(v,last=-1):
      dp[v][0] = 1
      dp[v][1] = 1
      for nv in edge[v]:
          if nv == last:
              continue
          dfs(nv, v)
          dp[v][0] = dp[v][0] * ((dp[nv][0] + dp[nv][1]) % MOD) % MOD
          dp[v][1] = dp[v][1] * dp[nv][0] % MOD


  dfs(1)
  print((dp[1][0] + dp[1][1])%MOD)
if __name__ == '__main__':
  main()
### BUGGY CODE ###

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

def kaijo(n):
    if n == 0:
        return 1
    else:
        num = 1
        for i in range(2, n+1):
            num = num * i
        return num

count = 0
num_AB = -1
while True:
    num_AB += 1
    if num_AB * (A+B) > K:
        break

    left_beauty = K - num_AB * (A+B)

    num_A = -1
    while True:
        num_A += 1
        # print("left_b: {}".format(left_beauty))
        if num_A * A > left_beauty:
            break
        elif num_A > N:
            break
        else:
            left_left_beauty = left_beauty - num_A * A

            if left_left_beauty % B == 0:
                num_B = int(left_left_beauty / B)
                num_nan = N - num_AB - num_A - num_B

                all_comb = kaijo(N)/(kaijo(num_AB)*kaijo(num_A)*kaijo(num_B)*kaijo(num_nan))
                count += int(all_comb)
                # print(num_A, num_B, num_AB, num_nan)
                # print(all_comb)

# print("=====")
print(count % 998244353)

### FIXED CODE ###

N, A, B, K = map(int, input().split(" "))
mod = 998244353
ncr = [1] * (N + 1)
v = 1

for i in range(N):
    v = (v * ((N - i) % mod) * pow((i + 1), mod - 2, mod)) % mod
    ncr[i + 1] = v % mod

pat = 0
for a in range(N + 1):
    if (K - (a * A) < 0):
        break
    if (K - (a * A)) % B == 0 and ((K - (a * A)) // B) <= N:
        pat += ncr[a] * ncr[(K - (a * A)) // B]
        pat %= mod

print(pat % mod)
### BUGGY CODE ###

import numpy as np

n, k, q = map(int, input().split())
i = np.array([k]*n)

# 計算
for l in range(q):
    a = int(input())-1
    i -= 1
    i[a] += 1

# 出力
[print('No') if i[m]<=0 else print('Yes') for m in range(n)]

### FIXED CODE ###

import numpy as np

n, k, q = map(int, input().split())
i = np.array([k-q]*n)

# 計算
for l in range(q):
    a = int(input())-1
    i[a] += 1

# 出力
[print('No') if i[m]<=0 else print('Yes') for m in range(n)]
### BUGGY CODE ###

N, k, Q = map(int, input().split())
A =[]
i = 0
j = 0
c = 0
 
def calc_de(n):
    return n - 1
 
for i in range(Q):
  A.append(int(input()))
 
S = [k]*N
 
for j in A:
    S = list(map(calc_de, S))
    S[j-1] += 1
 
for c in range(N):
    if S[c] > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

N, K, Q = map(int, input().split())

A = [K]*N
C = [0]*N

for r in range(Q):
    correct = int(input())
    C[correct-1] = C[correct-1] + 1

for i in range(N):
    A[i] = A[i] - Q + C[i]
    if A[i] > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

N, K = [int(x) for x in input().strip().split(" ")]
A = [int(x) for x in input().strip().split(" ")]

def mul(A):
    b = 1
    for a in A:
        b *= a
    return b

scores = [mul(A[i-K:i]) for i in range(N+1) if i >= K]
for i, S in enumerate(scores):
    if i == 0:
        continue
    if S > scores[i - 1]:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

N, K = [int(x) for x in input().strip().split(" ")]
A = [int(x) for x in input().strip().split(" ")]

for i in range(K, N):
    if A[i] > A[i-K]:
        print("Yes")
    else:
        print("No")