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

n,k=map(int, input().split())
h=list(map(int,input().split()))
dp=[(10**4)+1]*(n)
if k+1<=n:
  max=k+1
else:
  max=n
for i in range(1,max):
  dp[i]=abs(h[0]-h[i])

for i in range(n):
  if i+k+1<=n:
    max=k+1
  else:
    max=n-i
  for ik in range(1,max):
    if dp[i+ik] == (10**4)+1:
      dp[i+ik]=dp[i]+abs(h[i]-h[i+ik])
      continue
      
    if dp[i]+abs(h[i]-h[i+ik])<=dp[i+ik]:
      dp[i+ik]=dp[i]+abs(h[i]-h[i+ik])
    #print(dp)
    
print(dp[-1])

### FIXED CODE ###

n,k=map(int, input().split())
h=list(map(int,input().split()))
dp=[0]*(n)
if k+1<=n:
  max=k+1
else:
  max=n
  
for i in range(1,max):
  dp[i]=abs(h[0]-h[i])

for i in range(k,n):
  li=[abs(h[i]-h[ik])+dp[ik] for ik in range(i-1,i-k-1,-1) ]
  dp[i]=min(li)
  
print(dp[-1])
### BUGGY CODE ###

L = input()
l = len(L)
MOD = 10**9 + 7
ans = 0
c = 0
for k in range(l):
    if L[k] == "1":
        ans += (3**(l-k-1)) * (2**c)
        ans %= MOD
        c += 1
ans += 2**c
print(ans%MOD)

### FIXED CODE ###

L = input()
l = len(L)
MOD = 10**9 + 7
ans = 0
c = 0
for k in range(l):
    if L[k] == "1":
        ans += pow(3,l-k-1,MOD) * pow(2,c,MOD)
        ans %= MOD
        c += 1
ans += pow(2,c,MOD)
print(ans%MOD)
### BUGGY CODE ###

n = int(input())
left = 0
right = n
print(left)
sl = input()
if sl[0] == "V":
    quit()
while True:
    mid = (left + right) // 2
    print(mid)
    sm = input()
    if sm[0] == "V":
        quit()
    if ((mid - left) % 2) ^ sl != sm:
        left = mid
        sl = sm
    else:
        right = mid


### FIXED CODE ###

n = int(input())

left = 0
right = n
print(left, flush=True)
sl = input()
if sl[0] == "V":
    quit()
while right - left > 1:
    mid = (left + right) // 2
    print(mid, flush=True)
    sm = input()
    if sm[0] == "V":
        quit()

    if ((mid - left) % 2 == 1) ^ (sl == sm):
        left = mid
        sl = sm
    else:
        right = mid
### BUGGY CODE ###

import sys, math, itertools, collections, bisect 
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8') 
inf = float('inf') ;mod = 10**9+7 
mans = inf ;ans = 0 ;count = 0 ;pro = 1

from decimal import Decimal
a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())
if a == b:
    print("YES")
elif v <= w:
    print("NO")
elif a < b and w*t + b > v*t + a:
    print("NO")
elif a < b and -(w*t) + b < -(v*t) + a:
    print("NO")
else:
    now_a = a
    now_b = b
    for i in range(1, t+1):
        if now_a < now_b:
            now_a += v
            now_b += w
        else:
            now_a -= v
            now_b -= w
        if now_a == now_b:
            print("YES")
            exit()
        else:
            pass
    print("NO")

### FIXED CODE ###

a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())
if (v-w)*t >= abs(a-b):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

n = input()
a = [int(num) for num in input().split(" ")]

mod_value = 10**9 + 7

total = 0
for i in range(len(a)-1):
    target_value = 0
    for j in range(i+1, len(a)):
        target_value += a[j]
    total += a[i] * target_value 
print(total%mod_value)


### FIXED CODE ###

n = input()
a = [int(num) for num in input().split(" ")]

mod_value = 10**9 + 7

sum = 0
total = 0
for i in reversed(range(1, len(a))):
    sum += a[i]
    total += a[i-1] * sum

print(total%mod_value)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
B=[0]*Q
C=[0]*Q
for i in range(Q):
	B[i],C[i]=map(int,input().split())
for i in range(Q):
	S=0
	for j in range(N):
		if A[j]==B[i]:
			A[j]=C[i]
		S=S+A[j]
	print(S)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
Q=int(input())
B=[0]*Q
C=[0]*Q
for i in range(Q):
	B[i],C[i]=map(int,input().split())
import collections
A=collections.Counter(a)
S=0
for j in range(N):
	S=S+a[j]
for i in range(Q):
	if B[i] in A:
		f=A.pop(B[i])
		if C[i] in A:
			g=A[C[i]]
			h=f+g
		else:
			h=f
		A[C[i]]=h
	else:
		f=0
	S=S+f*(C[i]-B[i])
	print(S)
### BUGGY CODE ###

import bisect

def check(r,g,b):
    ans=0
    for i in range(len(r)):
        G=bisect.bisect_left(g,r[i])
        for j in range(G,len(g)):
            B=bisect.bisect_left(b,g[j])
            ans+=len(b)-B
            if 2*g[j]-r[i] in b:
                ans-=1
    return ans

N=int(input())
S=input()
ans=0
r=[]
g=[]
b=[]

for h in range(N):
    if S[h]=="R":
        r.append(h)
    elif S[h]=="G":
        g.append(h)
    else:
        b.append(h)

ans=check(r,g,b)+check(g,b,r)+check(b,r,g)+check(b,g,r)+check(g,r,b)+check(r,b,g)
print(ans)

### FIXED CODE ###

N=int(input())
S=input()
ans=S.count("R")*S.count("G")*S.count("B")
for i in range(N):
    for j in range(i+1,N):
        k=2*j-i
        if k<N and S[k]!=S[i] and S[k]!=S[j] and S[j]!=S[i]:
            ans-=1
print(ans)
### BUGGY CODE ###

A,B=map(int,input().split())
l=[]
ldi=[]
ans=""

a=A
while a<=B:
    l.append(format(a, 'b'))
    a+=1

i=0
while i<=B-A:
    ldi.append(l[i].zfill(len(format(B, 'b'))))
    i+=1

j=0
while j<=len(format(B, 'b'))-1:
    k=0
    p=0
    while k<=B-A:
        if ldi[k][j]=="1":
            p+=1
        else:
            pass
        k+=1
    if p%2==1:
        ans=ans+"1"
    else:
        ans=ans+"0"
    j+=1

print(int(ans, 2))

### FIXED CODE ###

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

def XOR(x):
    if x%4==1 or x%4==2:
        l="0"
    else:
        l="1"
    i=2
    while x>=(2**(i-1)):
        k=x%(2**i)
        if k<=2**(i-1)-1:
            l+="0"
        else:
            if k%2==0:
                l+="1"
            else:
                l+="0"
        i+=1    
    l=l[::-1]
    return(l)

b=XOR(B)
a=XOR(A-1).zfill(len(b))
ans=""

for j in range(len(b)):
    if b[j]==a[j]:
        ans+="0"
    else:
        ans+="1"

print(int(ans,2))
### BUGGY CODE ###

H,W = map(int,input().split())
S = [input() for i in range(H)]
ans = 0
def f(h,w):
    global H,W,S
    cnt = 1
    for ha in range(h-1,-1,-1):
        if S[ha][w]=="#":break
        cnt+=1
    for hb in range(h+1,H):
        if S[hb][w]=="#":break
        cnt+=1
    for wa in range(w-1,-1,-1):
        if S[h][wa]=="#":break
        cnt+=1
    for wb in range(w+1,W):
        if S[h][wb]=="#":break
        cnt+=1
    return cnt
for h in range(H):
    for w in range(W):
        if S[h][w]==".":
            ans = max(ans,f(h,w))
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
S = [input() for i in range(H)]

L = [[0]*W for i in range(H)]
R = [[0]*W for i in range(H)]
U = [[0]*W for i in range(H)]
D = [[0]*W for i in range(H)]
for h in range(H):
    for w in range(W):
        if S[h][w]==".":
            if h==0:D[h][w]=1
            else:D[h][w]=D[h-1][w]+1
            if w==0:R[h][w]=1
            else:R[h][w]=R[h][w-1]+1
for h in range(H-1,-1,-1):
    for w in range(W-1,-1,-1):
        if S[h][w]==".":
            if h==H-1:U[h][w]=1
            else:U[h][w]=U[h+1][w]+1
            if w==W-1:L[h][w]=1
            else:L[h][w]=L[h][w+1]+1

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans,L[h][w]+R[h][w]+U[h][w]+D[h][w]-3)
print(ans)
### BUGGY CODE ###

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

count=0
for i in range (A, B+1):
  if i % C ==0.:
    count +=1
print (count)

### FIXED CODE ###

a, b, x = map(int, input().split())
print(b // x - (a - 1) // x)
### BUGGY CODE ###

n=int(input())
S=input()
a=[0 for x in range(len(S))]

def zal(s):
  a[0]=len(s)
  i,j=1,0
  while i < a[0]:
    while i+j < a[0] and s[j]==s[i+j]:
      j+=1
    a[i]=j
    if j==0:
      i+=1
    else:
      k=1
      while i+k < a[0] and k+a[k] < j:
        a[i+k]=a[k]
        k+=1
      i+=k
      j-=k
  m=0
  for i in range(1,a[0]):
    if i >= a[i]:
      m=max(m,a[i])
  return m

m,i=0,0
while i < len(S)-1:
  m = max(m,zal(S[i:]))
  i += 1

print(m)


### FIXED CODE ###

n=int(input())
s=input()

m,j = 0,0
for i in range(n):
  if s[j:i+1] in s[i+1:]:
    m=i-j+1
  else:
    j+= 1

print(m)
### BUGGY CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import product
def main():
    n = int(input())
    s = input()

    r = [i for i, c in enumerate(s) if c == 'R']
    g = [i for i, c in enumerate(s) if c == 'G']
    b = [i for i, c in enumerate(s) if c == 'B']
    com = product(r, g, b)
    r = 0
    for c in com:
        r += c[0] < c[1] < c[2] and c[1] - c[0] != c[2] - c[1]
        r += c[0] < c[2] < c[1] and c[2] - c[0] != c[1] - c[2]
        r += c[2] < c[1] < c[0] and c[0] - c[1] != c[1] - c[2]
        r += c[2] < c[0] < c[1] and c[0] - c[2] != c[1] - c[0]
        r += c[1] < c[0] < c[2] and c[0] - c[1] != c[2] - c[0]
        r += c[1] < c[2] < c[0] and c[2] - c[1] != c[0] - c[2]
    print(r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    s = list(input())
    sr = [0] * n
    sg = [0] * n
    sb = [0] * n
    for i1 in range(n):
        ts = s[i1]
        if ts == 'R':
            sr[i1] = 1
        elif ts == 'G':
            sg[i1] = 1
        else:
            sb[i1] = 1
    if n <= 3:
        print(0)
        exit()
    r = 0
    for ia in range(0,n-3):
        ta = s[ia]
        if ta == 'R':
            r += sum(sg[ia+1:]) * sum(sb[ia+1:])
        elif ta == 'G':
            r += sum(sr[ia+1:]) * sum(sb[ia+1:])
        else:
            r += sum(sg[ia + 1:]) * sum(sr[ia + 1:])
        for ib in range((n - ia)//2+1):
            if ia + ib * 2 < n:
                if ta != s[ia + ib] and ta != s[ia + ib + ib] and s[ia+ib]!= s[ia + ib + ib]:
                    r -= 1
    print(r)

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

n=int(input())
sump=1

for i in range(n):
  sump*=i+1
  
print(sump%(1000000007))

### FIXED CODE ###

n=int(input())
sump=1

for i in range(n):
  sump*=i+1
  sump%=1000000007
  
print(sump)
### BUGGY CODE ###

class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] // self.fact[r] // self.fact[n - r]


from collections import defaultdict

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [a % M for a in A]

accA = [0] * (N + 1)
for i, a in enumerate(A, start=1):
    accA[i] = accA[i - 1] + a

cnt = defaultdict(int)
for a in accA:
    cnt[a % M] += 1

comb = Combination(N + 100)
ans = 0
for c in cnt.values():
    ans += comb.ncr(c, 2)

print(ans)

### FIXED CODE ###

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

S = [0] * (N+1)
for i in range(N) :
    S[i+1] = S[i] + A[i]

cat = {}
for s in S :
    mod = s % M
    if mod in cat :
        cat[mod] += 1
    else :
        cat[mod] = 1

def comb(n, k) :
    p = 1
    d = 1
    for i in range(k) :
        p *= (n - i)
        d *=(i + 1)
    return p // d

ans = 0
for key, val in cat.items() :
    if val < 2 :
        continue
    ans += comb(val, 2)

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

n = int(input())
a = list(map(int,input().split()))
for i,b in enumerate(a):
    for j in range(i+1,n):
        #print(b,a[j])
        if b == a[j]:
            print('NO')
            exit()
print('YES')

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
if n == len(set(a)):
  print('YES')
else:
  print('NO')
### BUGGY CODE ###

S = input()
cnt = 0

while True:
	if S.count('01') != 0:
		cnt += S.count('01')
		S=S.replace('01' , '')
	if S.count('10') != 0:
		cnt += S.count('10')
		S=S.replace('10' , '')

	if S.count('01') == 0 and S.count('10') == 0:
		print(cnt*2)
		exit()

### FIXED CODE ###

S = input()
cnt_1 = S.count('1')
cnt_0 = S.count('0')

print(min(cnt_1 , cnt_0) * 2)
### BUGGY CODE ###

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

for i in range(N):
  A[i] -= 1

loop_lis = [0]
for i in range(K):
  loop_lis.append(A[loop_lis[-1]])
  if len(loop_lis) != len(set(loop_lis)):
    break
for j in range(len(loop_lis)):
  if loop_lis[j] == loop_lis[-1]:
    break
if i == K-1:
  print(loop_lis[-1]+1)
else:
  print(loop_lis[j+(K-j)%(i+1-j)]+1)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
 
for i in range(N):
  A[i] -= 1

loop_lis = [0]
visited = [-1 for _ in range(N)]
visited[0] = 0
flag = 0
for i in range(K):
  if visited[A[loop_lis[-1]]] != -1:
    loop_time = i+1-visited[A[loop_lis[-1]]]
    start_loop = visited[A[loop_lis[-1]]]
    flag = 1
    break
  visited[A[loop_lis[-1]]] = i+1
  loop_lis.append(A[loop_lis[-1]])

if i == K-1 and flag == 0:
  print(loop_lis[-1]+1)
else:
  print(loop_lis[start_loop+(K-start_loop)%loop_time]+1)
### BUGGY CODE ###

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

L.sort()

count = 0
for i in range(0, N - 2):
    for p in range(i + 1, N - 1):
        for q in range(p + 1, N):
            if L[i] + L[p] > L[q]:
                count += 1
            else:
                break
print(count)

### FIXED CODE ###

import bisect

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

L.sort()

count = 0
for i in range(0, N - 2):
    for p in range(i + 1, N - 1):
        count += bisect.bisect_left(L, L[i] + L[p]) - p - 1
print(count)
### BUGGY CODE ###

from bisect import bisect

n = int(input())
a_list = sorted(map(int, input().split()))
b_list = sorted(map(int, input().split()))
c_list = sorted(map(int, input().split()))

b_c_table = [n - bisect(c_list, b) for b in b_list]

ans = 0
for a in a_list:
    i = bisect(b_list, a)
    ans += sum(b_c_table[i:n])
print(ans)


### FIXED CODE ###

from bisect import bisect
from itertools import accumulate

n = int(input())
a_list = sorted(map(int, input().split()))
b_list = sorted(map(int, input().split()))
c_list = sorted(map(int, input().split()))

b_c_table_ = list(accumulate(reversed(tuple(n - bisect(c_list, b) for b in b_list))))
b_c_table_.reverse()
b_c_table_ += [0]

print(sum(b_c_table_[bisect(b_list, a)] for a in a_list))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
def LI():return list(map(int,input().split()))
def yes():print("YES")
def no():print("NO")

n,k=LI()
a=LI()

import numpy as np


for _ in range(k):
    tab=[0]*(n+1)
    for i in range(n):
        q=a[i]
        if 0<=i-q:
            tab[i-q]+=1
        else:
            tab[0]+=1
        if i+q<=n-1:
            tab[i+q+1]-=1
        else:
            tab[n-1+1]-=1
    
    b=np.cumsum(tab)[:n]
    # print(tab,b)
    a=b[:]
print(*a)


### FIXED CODE ###

# coding: utf-8
# Your code here!
import time
t1=time.time()
def LI():return list(map(int,input().split()))
n,k=LI()
a=LI()

for _ in range(k):
    tab=[0]*(n)
    for i in range(n):
        q=a[i]
        if 0<=i-q:
            tab[i-q]+=1
        else:
            tab[0]+=1
        if i+q+1<=n-1:
            tab[i+q+1]-=1
        else:
            pass
    b=[tab[0]]
    for i in range(n-1):
        b.append(tab[i+1]+b[-1])
    a=b[:]
    if time.time()-t1>1.5:
        print(*a)
        exit()
print(*a)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
  N = int(input())
  ans = 0
  A = tuple(map(int,input().split()))
  for k in range(1,N):
    for i in range(0,N-k):
      if A[i]+A[i+k]==k:
        ans += 1
  print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from bisect import bisect_left
input = sys.stdin.readline
def main():
    N = int(input())
    ans = 0
    L = {}
    R = {}
    A = tuple(map(int,input().split()))
    for i,a in enumerate(A):
        if a+i in L:
            L[a+i] += 1
        else:
            L[a+i] = 1
        if i-a in R:
            R[i-a] += 1
        else:
            R[i-a] = 1
    for k in L:
        if k in R:
            ans += L[k]*R[k]
    print(ans)



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

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

if k==0:
    print(n**2)
    quit()

cnt=0
for a in range(k,n+1):
    b=list(range(k,n+1))
    cnt+=len(list(filter(lambda x: a%x>=k, b)))

print(cnt)


### FIXED CODE ###

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

s = 0
for b in range(1, n+1):
    s += max(0, b-k)*(n//b) + max(0, n%b-k+1)

if k == 0:
    s = n*n
print(s)
### BUGGY CODE ###

import numpy as np
import sys

input = sys.stdin.readline

n, t = map(int, input().split())
shops = [list(map(int, input().split())) for _ in range(n)]
shops.sort(reverse=True, key=lambda x: x[0]/(x[1]+1))
shops = np.array(shops, dtype=np.int64)

A0 = shops[:, 0] == 0
A1 = shops[:, 0] != 0

shopsA0 = shops[A0][:, 1] + 1
shopsA0.sort()

shops = shops[A1]

DP = np.array([t+10]*30, dtype=np.int64)
DP[0] = 0

for a, b in shops:
    np.minimum(DP[1:], (DP[:-1]+1)*(a+1)+b, out=DP[1:])

cumA0 = np.cumsum(shopsA0, dtype=np.int64)

DP = DP[DP <= t]
DPA0 = np.searchsorted(cumA0, t-DP, side='right')
ans = np.arange(len(DP)) + DPA0
print(ans.max())

### FIXED CODE ###

def main():
    import itertools
    import sys
    buf = sys.stdin.buffer


    n, t = map(int, buf.readline().split())
    m = map(int, buf.read().split())
    shops = []
    shopsA0 = [0]

    for a, b in zip(m, m):
        if a == 0:
            shopsA0.append(b + 1)
        else:
            shops.append([a / (b + 1), a, b])

    shopsA0.sort()
    shops.sort(reverse=True)


    DP = [t+10] * 30
    DP[0] = 0

    for _, a, b in shops:
        for num in range(28, -1, -1):
            candidate = (DP[num]+1) * (a+1) + b
            if candidate < DP[num+1]:
                DP[num+1] = candidate

    cumA0 = list(itertools.accumulate(shopsA0))

    ans = [0]
    count_A0 = len(cumA0) - 1
    for count, spend_time in enumerate(DP):
        residue = t - spend_time
        if residue < 0:
            break
        while count_A0 > 0 and cumA0[count_A0] > residue:
            count_A0 -= 1
        ans.append(count_A0 + count)
    print(max(ans))


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

from bisect import bisect_left, bisect_right

n, m, q = [int(x) for x in input().split()]

temp_list = []
for i in range(m):
    l, r = [int(x) for x in input().split()]
    temp_list.append((l, i, 0))
    temp_list.append((r, i, 1))
temp_list.sort()

for _ in range(q):
    l, r = [int(x) for x in input().split()]

    li = bisect_left(temp_list, (l, 0, 0))
    ri = bisect_right(temp_list, (r, m, 1))

    flag = [False] * m
    ans = 0
    for j in range(li, ri):
        _, i, f = temp_list[j]
        if f == 0:
            flag[i] = True
        elif f == 1 and flag[i]:
            ans += 1
    print(ans)

### FIXED CODE ###

n, m, q = [int(x) for x in input().split()]

t_list = [[0] * (n + 1) for i in range(n + 1)]
c_list = [[0] * (n + 1) for i in range(n + 1)]

for _ in range(m):
    l, r = [int(x) for x in input().split()]
    t_list[l][r] += 1

for i in range(1, n + 1):
    for j in range(1, n + 1):
        c_list[i][j] = t_list[i][j] + c_list[i][j - 1] + c_list[i - 1][j] - c_list[i - 1][j - 1]

for _ in range(q):
    l, r = [int(x) for x in input().split()]
    print(c_list[r][r] - c_list[l - 1][r] - c_list[r][l - 1] + c_list[l - 1][l - 1])
### BUGGY CODE ###

from fractions import gcd
N,A,B,K=map(int,input().split())
mod=998244353

Factorial=[1]*(N+1)
for i in range(1,N+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod

inverseFactorial=[1]*(N+1)
inverseFactorial[N]=power(Factorial[N],mod-2)
for i in range(0,N)[::-1]:
  inverseFactorial[i]=(inverseFactorial[i+1]*(i+1))%mod
  
def f(i,j):
  if i>j:
    i,j=j,i
  res=0
  if j<=N:
    for k in range(max(0,i+j-N),i+1):
      t=Factorial[N]
      t=(t*inverseFactorial[i-k])
      t=(t*inverseFactorial[j-k])
      t=(t*inverseFactorial[k])
      t=(t*inverseFactorial[N-i-j+k])%mod
      res+=t
  return res%mod
      
ans=0
g=gcd(A,B)
if K%g==0:
  A,B,K=A//g,B//g,K//g
else:
  print(0)
  exit()
x0,y0=-1,-1
for i in range(K//A+1):
  if (K-A*i)%B==0:
    x0=i
    y0=(K-A*i)//B
    break

for m in range(max(0,(y0-N)//A),min(y0//A+1,(N-x0)//B+1)):
  ans+=f(x0+B*m,y0-A*m)
  ans%=mod
  
    
print(ans%mod)

  

### FIXED CODE ###

N,A,B,K=map(int,input().split())
mod=998244353

Factorial=[1]*(N+1)
for i in range(1,N+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod

inverseFactorial=[1]*(N+1)
inverseFactorial[N]=power(Factorial[N],mod-2)
for i in range(0,N)[::-1]:
  inverseFactorial[i]=(inverseFactorial[i+1]*(i+1))%mod
  
def comb(x,y):
  if x<y:
    return 0
  return (Factorial[x]*inverseFactorial[y]*inverseFactorial[x-y])%mod
      
ans=0  
for i in range(K//A+1):
  if (K-A*i)%B==0:
    j=(K-A*i)//B
    ans+=comb(N,i)*comb(N,j)
    ans%=mod
  

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

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

for i in range(0,K):
  if abs(X-D) > abs(X+D):
    X = X+D
  else:
    X = X-D
    
print(abs(X))

### FIXED CODE ###

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

if abs(X) > K*D:
    X = abs(X) - K*D
else:
    # とりあえず同方向に移動できるところまでいく
    # 移動回数
    T = abs(X)//D
    # 移動先の座標
    Y = abs(X)%D
    
    # 残りは往復の2択
    X = abs(Y - ((K-T)%2)*D)   
    
print(X)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    A = []
    tmp = (0,)*(N+1)
    A.append(tmp)
    for i in range(N):
        tmp = (0,) + tuple(map(int, input().split()))
        A.append(tmp)
    B = [1]*(N+1)
    C = [[0]*N for i in range(N+1)]
    count = 0
    flag = 0
    D = []
    for i in range(1,N+1):
        D.append(i)
        
    while count < N*(N-1)//2 and flag == 0:
        flag = 1
        for i in D:
            if B[i] < N:
                j = A[i][B[i]]
                if A[j][B[j]] == i:
                    k = max(C[i][B[i]-1], C[j][B[j]-1]) + 1
                    C[i][B[i]] = k
                    C[j][B[j]] = k
                    B[i] += 1
                    if B[i] == N:
                        D.remove(i)
                    B[j] += 1
                    if B[j] == N:
                        D.remove(j)
                    count += 1
                    flag = 0
                    
    #print(C)
    ans = 0
    for i in C:
        if i[-1] > ans:
            ans = i[-1]
    if ans == 0:
        print(-1)
    else:
        print(ans)
    
    
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    A = []
    tmp = (0,)*(N+1)
    A.append(tmp)
    for i in range(N):
        tmp = (0,) + tuple(map(int, input().split()))
        A.append(tmp)
    B = [1]*(N+1)
    C = [[0]*N for i in range(N+1)]
    count = 0
    flag = 0
    
    #1試合目
    Q = []
    nextQ = []
    for i in range(1,N+1):
        j = A[i][B[i]]
        if A[j][B[j]] == i:
            ii = min(i,j)
            jj = max(i,j)
            if not (ii,jj) in nextQ:
                nextQ.append((ii,jj))
    
    day = 0    
    while count < N*(N-1)//2 and len(nextQ) >= 1:
        day += 1
        Q = nextQ
        nextQ = []
        for T in Q:
            i = T[0]
            j = T[1]
            k = max(C[i][B[i]-1], C[j][B[j]-1]) + 1
            C[i][B[i]] = k
            C[j][B[j]] = k
            B[i] += 1
            B[j] += 1
            count += 1
            if B[i] < N:
                I = A[i][B[i]]
                if A[I][B[I]] == i:
                    ii = min(i,I)
                    jj = max(i,I)
                    if not (ii,jj) in nextQ:
                        nextQ.append((ii,jj))
            if B[j] < N:
                J = A[j][B[j]]
                if A[J][B[J]] == j:
                    ii = min(j,J)
                    jj = max(j,J)
                    if not (ii,jj) in nextQ:
                        nextQ.append((ii,jj))
            
                    
    #print(C)
    if count < N*(N-1)//2:
        print(-1)
    else:
        print(day)
    
    
    
if __name__ == '__main__':
    main()