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


from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools




def main():
    num = int(input())
    data = [int(input()) for i in range(num)]

    mod = 998244353

    dp = [defaultdict(int) for i in range(num)]
    dp2 = [defaultdict(int) for i in range(num)]
    for i in range(num):
        now_num = data[i]
        if i == 0:
            dp[i][0] = 2
            dp[i][now_num] = 1
            dp2[i][0] = 1
            dp2[i][now_num] = 1
            continue
        for key in dp[i - 1].keys():
            dp[i][key] += dp[i - 1][key] * 2
            dp[i][key + now_num] += dp[i - 1][key]
            dp[i][key] %= mod
            dp[i][key + now_num] %= mod
            dp2[i][key] += dp2[i - 1][key]
            dp2[i][key + now_num] += dp2[i - 1][key]
            dp2[i][key] %= mod
            dp2[i][key + now_num] %= mod

    ans = pow(3, num, mod)
    hikukazu = 0
    sum_num = sum(data)
    for key in dp[num - 1].keys():
        if key >= math.ceil(sum_num / 2):
            hikukazu += dp[num - 1][key]
    if sum_num % 2 == 0:
        hikukazu -= dp2[num - 1][sum_num // 2]
    ans -= hikukazu * 3
    ans %= mod
    print(ans)


if __name__ == '__main__':
    main()



### FIXED CODE ###

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

import numpy as np
MOD = 998244353

N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)

# 赤の和がS/2以上となるものを求めて3倍
# 和に対して何通りあるのか

dp = np.zeros(S+1, dtype=np.int64)
dp[0] = 1
for a in A:
    prev = dp
    dp = prev * 2 # 赤以外を採用
    dp[a:] += prev[:-a] # 赤
    dp %= MOD

answer = pow(3,N,MOD) - dp[(1+S)//2:].sum() * 3
# 2色が反例となる場合を引きすぎている
if S % 2 == 0:
    dp = np.zeros(S+1, dtype=np.int64)
    dp[0] = 1
    for a in A:
        dp[a:] += dp.copy()[:-a]
        dp %= MOD
    answer += dp[S//2] * 3
answer %= MOD
print(answer)
### BUGGY CODE ###

N=int(input())
List = list(map(int, input().split()))
res = 0
flagWhile = True
flagManip = True
while flagWhile:
  for i in range(N):
    if flagManip:
      if List[i] % 2 == 0:
        List[i] = List[i] //2
        flagManip = False
        pass
    List[i] = List[i] * 3
  if flagManip:
    flagWhile = False
  flagManip = True
  if flagWhile:
    res += 1
print(res)

### FIXED CODE ###

N=int(input())
List = list(map(int, input().split()))
res = 0
flagWhile = True
flagManip = True
for i in range(N):
  while List[i] % 2 == 0:
    List[i] = List[i] //2
    res += 1

print(res)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

a_list = []

for index in range(m):
    a_list.append(int(input()))

ans_list = []

ans_list = [0] * (n + 1)

for index in range(n + 1):
    if index == 0:
        ans_list[index] += 1
        continue
    if index == 1 and (index not in a_list):
        ans_list[index] += ans_list[index - 1]
        continue

    if index not in a_list:
        if (index - 1) not in a_list:
            ans_list[index] += ans_list[index - 1]
            ans_list[index] %= 1000000007
        if (index - 2) not in a_list:
            ans_list[index] += ans_list[index - 2]
            ans_list[index] %= 1000000007

print(ans_list[n])


### FIXED CODE ###

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

a_set=set()

for index in range(m):
    a_set.add(int(input()))

ans_list=[]

for index in range(n + 1):
    ans_list.append(0)

for index in range(n + 1):
    if index == 0:
        ans_list[index] += 1
        continue
    if index == 1 and (index not in a_set):
        ans_list[index] += ans_list[index - 1]
        continue
    
    if index not in a_set:
        if (index - 1) not in a_set:
            ans_list[index] += ans_list[index - 1]
            ans_list[index] %= 1000000007
        if (index - 2) not in a_set:
            ans_list[index] += ans_list[index - 2]
            ans_list[index] %= 1000000007

print(ans_list[n])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
cnt = 0
for i in range(n):
    for k in range(i+1, n):
        if a[i] > a[k]:
            cnt += 1
print(cnt)


### FIXED CODE ###

# Merge Sortを元に分割統治で反転数を求める
cnt = 0
def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = [A[i] for i in range(left, mid)]
    R = [A[i] for i in range(mid, right)]
    L.append(float("inf"))
    R.append(float("inf"))
    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
# R[j]について，Lに含まれマージ後にR[j]よりも後に移動するような要素の数
            cnt += n1 - i
            A[k] = R[j]
            j += 1

def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)

input()
a = list(map(int, input().split()))
merge_sort(a, 0, len(a))
print(cnt)
### BUGGY CODE ###

N=int(input())
data = list(map(int, input().split()))
ans=1
if N==1:
    ans=1
elif N>1:
    for i in range(1,N):
        count=0
        for k in range(0,i+1):
            if data[i]<=data[i-k]:
                count+=1
                if count==i+1:
                    ans+=1
                    #print("I=",i)
                    break
            elif data[i]>data[i-k]:
                break


print(ans)

### FIXED CODE ###

N=int(input())
data = list(map(int, input().split()))
ans=1
minmin=data[0]
if N==1:
    ans=1
elif N>1:
    minmin=data[0]
    for i in range(1,N):

        if data[i]<=minmin:
            minmin=data[i]
            #if minmin<=data[i]:
            ans+=1
                #continue
        #if minmin<=data[i]:
            #ans+=1

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

def signed_area(p1, p2, p3):
    '''符号付き面積を計算 '''

    area = (((p2[0] - p1[0]) * (p3[1] - p1[1])) - ((p3[0] - p1[0]) * (p2[1] - p1[1]))) / 2
    return area


def convex_hull(p_list):
    '''グラハムの凸包走査 '''

    p_sort = []
    for i in p_list:
        p_sort.append(i[0])

    # x座標が最小のものをリストの先頭に配置。
    min_index = p_sort.index(min(p_sort))
    min_p = p_list.pop(min_index)
    p_list.insert(0, min_p)

    # 座標最小の点と他の点との角度順にソート ソートアルゴリズムに選択の余地が有る。
    p_length = len(p_list)
    count = 0
    index = 0
    while True:
        count += 1
        index += 1

        area_sign = signed_area(p_list[0], p_list[index], p_list[index + 1])

        # 符号付き面積が負ならば点を入れ替え
        if area_sign < 0:
            p_list[index], p_list[index + 1] = p_list[index + 1], p_list[index]
            count = 0

        if count == p_length - 1:
            break

        if index == p_length - 2:
            index = 0

    # 凹部の点を削除する。
    index = -1
    count = 0
    while True:
        index += 1
        count += 1

        area_sign = signed_area(p_list[index], p_list[index + 1], p_list[index + 2])
        if area_sign < 0:
            del p_list[index + 1]
            count = 0

        if count == len(p_list):
            break

        if index >= len(p_list) - 3:
            index = -1
    return p_list

n = int(input())
point = []
for _ in range(n):
    x, y = map(int, input().split())
    point.append([x, y])

if n == 2:
    point.append(point[1])
point = convex_hull(point)
ans = 0
for i in range(len(point)):
    for j in range(len(point)):
        if i != j:
            ans = max(ans, abs(point[i][0] - point[j][0]) + abs(point[i][1] - point[j][1]))
print(ans)            


### FIXED CODE ###

n = int(input())
x_list = []
y_list = []
for _ in range(n):
    x, y = map(int, input().split())
    x_list.append(x - y)
    y_list.append(x + y)
x_list.sort()
y_list.sort()
ans = max(x_list[-1] - x_list[0], y_list[-1] - y_list[0])
print(ans)
### BUGGY CODE ###

def main():
    n=int(input())
    a=[list(map(int,input().split())) for _ in [0]*n]
    m=(n*(n-1))//2
    d=dict()
    dr=[]
    cnt=0
    for i in range(n-1):
        for j in range(i+1,n):
            d[(i,j)]=cnt
            dr.append((i,j))
            cnt+=1
    #print(d)
    #print(dr)
    g=[[] for _ in [0]*m]
    gr=[0]*m
    for i in range(n):
        temp=[]
        for j in a[i]:
            j-=1
            if i>j:temp.append(d[(j,i)])
            else:temp.append(d[(i,j)])
        for j in range(len(temp)-1):
            g[temp[j]].append(temp[j+1])
            gr[temp[j+1]]+=1
    #print(g)
    #print(gr)
    q=[]
    for i in range(m):
        if gr[i]==0:
            q.append(i)
    cnt=0
    #print(q)
    while q:
        cnt+=1
        qq=[]#次回に回す分
        temp=[]#今回試合する分
        s=set()#戦うチーム
        while q:#今回の試合を抽出
            i=q.pop()
            x,y=dr[i]
            if (x not in s) and (y not in s):
                temp.append(i)
                s.add(x)
                s.add(y)
            else:
                qq.append(i)
        #print(temp,"t")
        while temp:
            i=temp.pop()
            for j in g[i]:
                gr[j]-=1
                if gr[j]==0:
                    qq.append(j)
        #print(qq)
        q=qq
    if sum(gr)==0:
        print(cnt)
    else:
        print(-1)



main()

### FIXED CODE ###

def main():
    n=int(input())
    a=[list(map(int,input().split())) for _ in [0]*n]
    m=(n*(n-1))//2
    d=dict()
    dr=[]
    cnt=0
    for i in range(n-1):
        for j in range(i+1,n):
            d[(i,j)]=cnt
            dr.append((i,j))
            cnt+=1
    #print(d)
    #print(dr)
    g=[[] for _ in [0]*m]
    gr=[0]*m
    for i in range(n):
        temp=[]
        for j in a[i]:
            j-=1
            if i>j:temp.append(d[(j,i)])
            else:temp.append(d[(i,j)])
        for j in range(len(temp)-1):
            g[temp[j]].append(temp[j+1])
            gr[temp[j+1]]+=1
    #print(g)
    #print(gr)
    q=[]
    for i in range(m):
        if gr[i]==0:
            q.append(i)
    cnt=0
    #print(q)
    while q:
        cnt+=1
        qq=[]#次回に回す分
        temp=[]#今回試合する分
        s=set()#戦うチーム
        while q:#今回の試合を抽出
            i=q.pop()
            x,y=dr[i]
            if (x not in s) and (y not in s):
                temp.append(i)
                s.add(x)
                s.add(y)
            else:
                qq.append(i)
        #print(temp,"t")
        while temp:
            i=temp.pop()
            for j in g[i]:
                gr[j]-=1
                if gr[j]==0:
                    qq.append(j)
        #print(qq)
        q=qq
    if sum(gr)==0:
        print(cnt)
    else:
        print(-1)



main()
### BUGGY CODE ###

import bisect
from collections import deque
import sys
input = sys.stdin.readline
x,y,a,b,c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort()
q.sort()
r.sort(reverse=True)
red_que = p[a-x:]
green_que = q[b-y:]
red_count = 0
green_count = 0
for i in range(c):
    if red_que[red_count] < green_que[green_count]:
        if red_que[red_count] < r[i]:
            red_que[red_count] = 0
            red_count += 1
            bisect.insort_left(red_que, r[i])
        else:
            break
    else:
        if green_que[green_count] < r[i]:
            green_que[green_count] = 0
            green_count += 1
            bisect.insort_left(green_que, r[i])
        else:
            break
print(sum(green_que) + sum(red_que))

### FIXED CODE ###

import heapq
from collections import deque
import sys
input = sys.stdin.readline
x,y,a,b,c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort()
q.sort()
r.sort(reverse=True)
red_que = p[a-x:]
heapq.heapify(red_que)
green_que = q[b-y:]
heapq.heapify(green_que)
for i in range(c):
    re_mi = heapq.heappop(red_que)
    gr_mi = heapq.heappop(green_que)
    if re_mi < gr_mi:
        if re_mi < r[i]:
            heapq.heappush(red_que,r[i])
            heapq.heappush(green_que,gr_mi)
        else:
            heapq.heappush(green_que,gr_mi)
            heapq.heappush(red_que,re_mi)
            break
    else:
        if gr_mi < r[i]:
            heapq.heappush(red_que,re_mi)
            heapq.heappush(green_que,r[i])
        else:
            heapq.heappush(green_que,gr_mi)
            heapq.heappush(red_que,re_mi)
            break
print(sum(green_que) + sum(red_que))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)

# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

def main():
	N, M = map(int, input().split(" "))
	#N = int(input())
	#S = input()

	A = input().split(" ")
	A = list(A)
	#A = A[:-1]
	A = [int(s) * (-1) for s in A]

	BC = []
	for i in range(M):
		b, c = map(int, input().split(" "))
		BC.append((c, b))

	heapq.heapify(A)

	for i in BC:
		c, b = i
		for i in range(b):
			heapq.heappush(A, c * (-1))
	
	ans = 0
	for i in range(N):
		tmp = heapq.heappop(A) * (-1)
		ans += tmp
		#print(tmp)
	print(ans)

if __name__ == "__main__":
	main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)

# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

def main():
	N, M = map(int, input().split(" "))
	#N = int(input())
	#S = input()

	A = input().split(" ")
	A = list(A)
	#A = A[:-1]
	A = [(int(s) * (-1), 1) for s in A]
	heapq.heapify(A)

	for i in range(M):
		b, c = map(int, input().split(" "))
		heapq.heappush(A, (c * (-1), b))
	
	ans = []
	for i in range(N):
		t, con = heapq.heappop(A)
		for _ in range(con):
			if len(ans) == N:
				print(sum(ans))
				sys.exit()
			ans.append(t * (-1))
	print(sum(ans))


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

def main():
    N,K=map(int,input().split())
    h=list(map(int,input().split()))
    dp=[10**10]*N
    dp[0]=0
    for i in range(N):
        for j in range(1,min(K+1,N-i)):
            dp[i+j]=min(dp[i+j],dp[i]+abs(h[i]-h[i+j]))
    print(dp[N-1])

if __name__=="__main__":
    main()

### FIXED CODE ###

def main():
    N,K=map(int,input().split())
    h=list(map(int,input().split()))
    dp=[10**10]*N
    dp[0]=0
    for i in range(N):
        for j in range(1,min(K+1,N-i)):
            dp[i+j]=min(dp[i+j],dp[i]+abs(h[i]-h[i+j]))
    print(dp[N-1])

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

n=int(input())
s=list(input() for _ in range(n))

t=['']*n

for i in range(n):
	t[i]=sorted(s[i])

cnt=0

for i in range(n-1):    
	for j in range(i+1,n):    
		if t[i]==t[j]:
			cnt+=1

print(cnt)

### FIXED CODE ###

n=int(input())
s=list(input() for _ in range(n))

t=['']*n

for i in range(n):
	t[i]=sorted(s[i])

u=sorted(t)

cnt=0

#for i in range(n-1):    
#	for j in range(i+1,n):
#		if u[i]!=u[j]:
#			break
#		else:
#			cnt+=1

cnt_a=0
cnt_b=0

u.append(['0'])

#print(u)


for i in range(n):
	if u[i+1]==u[i]:
		cnt_a+=1
		#print(cnt_a)
	else:
		if cnt_a>0:
			cnt_b+=(cnt_a+1)*cnt_a//2
			#print(cnt_b)
			cnt_a=0

print(cnt_b)
### BUGGY CODE ###

from collections import deque
import numpy as np

def bfs():
    #max = 0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([])
    for i in slist:
        que.append((i[0], i[1]))
        d[i[0]][i[1]] = 0


    while que:
        p = que.popleft()

        for i in range(4):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]
            #a = temp[ny][nx]
            if 0<=nx<W and 0<=ny<H and maze[ny][nx]!="#":
                #que.append((nx))
                temp[ny][nx] = d[p[0]][p[1]] + 1
                a = temp[ny][nx]
                #d[ny][nx] = d[p[0]][p[1]] + 1
                if a < d[ny][nx]:
                    que.append((ny, nx))
                    d[ny][nx] = a
                    #if max < d[ny][nx]:
                        #max = d[ny][nx]

    return np.max(np.array(d))

H, W = map(int, input().split())
d = [[float("inf")]*W for i in range(H)]
temp = [[float("inf")]*W for i in range(H)]
maze = [list(input()) for i in range(H)]

slist = []
for i in range(H):
    for j in range(W):
        if maze[i][j]=="#":
            slist.append((i,j))



#for i in slist:
#    s = bfs(i[0], i[1])

print(bfs())
#print(s)


### FIXED CODE ###

from collections import deque

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

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)
### BUGGY CODE ###

def solve(A, m):
	if m==0:
		return True
	if len(A) == 0:
		return False
	if m < 0:
		return False
	else:
		return (solve(A[1:], m) or solve(A[1:], m-int(A[0])))


def main():
	n = int(input())
	A = input()
	A = A.split()
	q = int(input())
	ms= input()
	for m in ms.split():
		if solve(A, int(m)):
			print('yes')
		else:
			print('no')

if __name__ == '__main__':
	main()

### FIXED CODE ###

def power_set(A, s):
	if len(A) == 0:
		return {s}
	else:
		return power_set(A[1:], s) | power_set(A[1:], s+A[0])

def main():
	n = int(input())
	A = input()
	#print(n)
	A = list(map(int, A.split()))
	q = int(input())
	m = input()
	ms = list(map(int, m.split()))
	powerset = power_set(A, 0)
	
	for m in ms:
		if m in powerset:
			print('yes')
		else:
			print('no')

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

import math
import time

prime_numbers = set()


def is_primenumber(x):
    if x in prime_numbers:
        return True
    if x == 1:
        return False
    elif x == 2:
        prime_numbers.add(2)
        return True
    else:
        for i in range(2, int(math.sqrt(x)) + 1):
            if x % i == 0:
                return False
        prime_numbers.add(x)
        return True


def query(l, r):
    count = 0
    for x in range(l, r + 1, 2):
        if is_primenumber(x) and is_primenumber((x + 1) // 2):
            count += 1
    print(count)


# e = time.time()
# print(e - s)
if __name__ == "__main__":
    for i in range(1, 10 ** 5 + 1):
        is_primenumber(i)
    Q = int(input())

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

### FIXED CODE ###

import math
import itertools
import sys

prime_numbers = set()
table = [0 for i in range(10 ** 5 + 1)]
input = lambda: sys.stdin.readline().strip()


def is_primenumber(x):
    if x in prime_numbers:
        return True
    if x == 1:
        return False
    elif x == 2:
        prime_numbers.add(2)
        return True
    else:
        for i in range(2, int(math.sqrt(x)) + 1):
            if x % i == 0:
                return False
        prime_numbers.add(x)
        return True


def is_like_2017(x):
    return is_primenumber(x) and is_primenumber((x + 1) // 2)


def query(l, r):
    print(table[r] - table[l - 1])


if __name__ == "__main__":
    for i in range(1, 10 ** 5 + 1, 2):
        if is_like_2017(i):
            table[i] += 1
    table = [x for x in itertools.accumulate(table)]
    Q = int(input())

    for _ in range(Q):
        l, r = [int(x) for x in input().split(" ")]
        query(l, r)
### BUGGY CODE ###

import sys #追加
sys.setrecursionlimit(10**9)

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

#a,bの最大公約数
def gcd(a, b):
   while b:
       a, b = b, a % b
   return a

#a,bの最小公倍数
def lcm(a, b):
   return a * b // gcd (a, b)


bl = [i//2 for i in al]
from fractions import gcd
ans = 1
for b in bl:
   ans = (ans * b) // gcd(ans, b)

for a in al:
   if ans % a == 0:
      print(0)
      import sys
      sys.exit()

def ceil(a, b):
   return a // b + (a % b > 0)

print(ceil(m // ans, 2))


### FIXED CODE ###

import sys #追加
sys.setrecursionlimit(10**9)
import time
s = time.time()

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

bl = [i//2 for i in al]
from fractions import gcd
ans = 1
for b in bl:
   if time.time() - s > 1.9:
      print(0)
      import sys
      sys.exit()
   ans = (ans * b) // gcd(ans, b)

for a in al:
   if time.time() - s > 1.9:
      print(0)
      import sys
      sys.exit()
   if ans % a == 0:
      print(0)
      import sys
      sys.exit()

def ceil(a, b):
   return a // b + (a % b > 0)

print(ceil(m // ans, 2))
### BUGGY CODE ###

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

ans = 0
for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i+j+l == s:
                ans += 1

print(ans)

### FIXED CODE ###

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

ans = 0
for i in range(k+1):
    for j in range(k+1):
        if 0 <= s-i-j <= k:
            ans += 1

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

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

dp = [0] * N
dp [0] = 0

for j in range (1, N):
    dp_list = []
    for k in range (1, K+1- max(0,K-j)):
        dp_list.append(dp[j-k] + abs(h[j]-h[j-k]))
    dp[j] = min(dp_list)
print(dp[N-1])

### FIXED CODE ###

import numpy as np
N, K= map(int,input().split())
h = list(map(int,input().split()))
 
dp = [0] * N
h = np.array(h)
 
dp = np.array([0]*N, dtype=np.int64)
 
for i in range (1, N):
    x = max(0, i - K)
    dp[i] = np.min(dp[x:i] + np.abs(h[i]-h[x:i]))
print(dp[N-1])
### BUGGY CODE ###

"""
F
"""
import sys
input=sys.stdin.readline
mod=10**9+7
MAX=2*10**6+100

g1=[1,1]
g2=[1,1]
for i in range(2,MAX+1):
    num_1=g1[-1]*i%mod
    g1.append(num_1)
    g2.append(pow(num_1,mod-2,mod))
    
def cmb(n,r):
    return g1[n]*g2[r]*g2[n-r]%mod

r1,c1,r2,c2=map(int,input().split())
if r2-r1<c2-c1:
    c1,r1=r1,c1
    c2,r2=r2,c2

S=cmb(r1+c1,r1)
ans=S
table1=[]
table2=[]
num1=c1+1
num2=r1+1
for i in range(c2-c1):
    S=(2*S+cmb(num1+i+r1-1,r1-1)+cmb(num2+i+c1-1,c1-1))%mod
    ans=(ans+S)%mod  
    
num1=r1
num2=r1+c2-c1+1
for i in range(r2-(r1+c2-c1)):
    S=(2*S-cmb(num1+i+c2,c2)+cmb(num2+i+c1-1,c1-1))%mod
    ans=(ans+S)%mod  
    
num1=c1
num2=r2-(c2-c1)
for i in range(c2-c1):
    S=(2*S-cmb(num1+i+r2,r2)-cmb(num2+i+c2,c2))%mod
    ans=(ans+S)%mod  

print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline

mod=10**9+7
MAX=2*10**6+100

g1=[1,1]
g2=[1,1]
for i in range(2,MAX+1):
    num_1=g1[-1]*i%mod
    g1.append(num_1)
    g2.append(pow(num_1,mod-2,mod))
    
def cmb(n,r):
    return g1[n]*g2[r]*g2[n-r]%mod

def g(x,y):
    return cmb(x+y+2,y+1)-1

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

num=(g(r2,c2)-g(r2,c1-1)-g(r1-1,c2)+g(r1-1,c1-1))%mod
print(num)