Harryxun/stf_run huggingface dataset:
import copy

def main():
    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a%b)

    def lcm(a, b):
        return (a // gcd(a, b)) * b

    n, m = map(int, input().split())
    # これだと72がREになる
    A = set([int(x) for x in input().split()])
    # これだと74も78もREになる
    # A = [int(x) for x in input().split()]
    # A_ = copy.deepcopy(A)
    # a_lcm = A.pop()
    a_lcm = 1
    # Aの要素が複数ならlcmを計算する
    #if len(A) >= 1:
    for a in A:
        a_lcm = lcm(a_lcm, a)
    #else:
    #    a_lcm = a_lcm
    # 元のAの値とlcmの半分の値を割り切れるものがあったら0
    #for i in A_:
    for i in A:
        if (a_lcm / 2) % i == 0:
        # if (a_lcm / i) % 2 == 0: 
            print(0)
            exit()
        # else:
        #     continue
    # mがlcmの半分よりも小さかったら0
    if (a_lcm / 2) > m:
    # if a_lcm > m * 2:
        print(0)
        exit()
    # else:
    # # あとは定数倍の数調べて終わり
    # ans = int((m - (a_lcm / 2))) // a_lcm + 1
    ans = int((m - (a_lcm / 2)) // a_lcm) + 1
    print(ans)
    
        # a_lcm = a_lcm // 2
        # q = m // a_lcm
        # if q % 2 == 0:
        #     ans = q // 2
        # else:
        #     ans = q // 2 + 1
        # print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import copy
# from math import gcd


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def lcm(a, b):
    return (a // gcd(a, b)) * b
def main():
    n, m = map(int, input().split())
    A = set([int(x) for x in input().split()])
    a_lcm = 1
    for a in A:
        a_lcm = lcm(a_lcm, a)
        # mがlcmの半分よりも小さかったら0
        if (a_lcm / 2) > m:
            print(0)
            exit()
    for a in A:
        if (a_lcm / 2) % a == 0:
            print(0)
            exit()
    # # あとは定数倍の数調べて終わり
    ans = int((m - (a_lcm / 2)) // a_lcm) + 1
    print(ans)

if __name__ == '__main__':
    main()
n,k,*a=map(int,open(i:=0).read().split())
a.sort()
s=b=~k%2or(p:=a.pop)()
while k>1:
 if(x:=a[i]*a[i+1])*b>a[-1]*a[-2]*b:i+=2
 else:x=p()*p()
 s=s*x%(10**9+7);k-=2
print(s)

### FIXED CODE ###

def main():
    M=10**9+7
    n,k,*a=map(int,open(0).read().split())
    x,y=[],[]
    for i in a:
        if i>0:x+=i,
        if i<0:y+=i,
    if len(x)+len(y)<k or k%2 and not x and len(y)<n:
        print(0)
        return
    if n==k or k%2 and not x:
        c=1
        for i in sorted(x+y)[-k:]:
            c=c*i%M
        print(c)
        return
    x=sorted(x)[::-1][:k]
    i=len(x)
    y.sort()
    m=len(y)
    j=k-i
    if j%2:
        x=x[:-1]
        i-=1
        j+=1
    x+=y[:j]
    while i>1 and j+1<m and x[i-1]*x[i-2]<y[j]*y[j+1]:
        x[i-1],x[i-2]=y[j],y[j+1]
        i-=2
        j+=2
    c=1
    for i in x:
        c=c*i%M
    print(c)
main()
N = int(input())
A = list(map(int, input().split()))
acts = [(x, i) for i, x in enumerate(A)]
acts.sort()
dp = [[-1]*N for _ in range(N)]

def solve(l, r):
    if r < l:
        return 0
    if dp[l][r] >= 0:
        return dp[l][r]
    k = r - l
    act, init_pos = acts[k]
    gain_l = act * abs(l - init_pos)
    gain_r = act * abs(r - init_pos)
    res = dp[l][r] = max(gain_l + solve(l+1, r), gain_r + solve(l, r-1))
    return res

print(solve(0, N-1))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
N = int(input())
A = list(map(int, input().split()))
acts = [(x, i) for i, x in enumerate(A)]
acts.sort()
dp = [[-1]*N for _ in range(N)]
 
def solve(l, r):
    if r < l:
        return 0
    if dp[l][r] >= 0:
        return dp[l][r]
    k = r - l
    act, init_pos = acts[k]
    gain_l = act * abs(l - init_pos)
    gain_r = act * abs(r - init_pos)
    res = dp[l][r] = max(gain_l + solve(l+1, r), gain_r + solve(l, r-1))
    return res
 
print(solve(0, N-1))
# -*- coding:utf-8 -*-
n, m = map(int, input().strip().split())
ans = 0
f_one = False
for i in range(m):
    tmp_d, tmp = map(int, input().strip().split())
    if tmp_d == 1:
      f_one = True
      
    if ((tmp_d == 1) and (tmp == 0)):
        ans = -1
        break
    elif (tmp_d in digit.keys()) and (digit[tmp_d] != tmp):
        ans = -1
        break
    else:
        ans += tmp*(10**(n-tmp_d))
      
if not f_one:
	ans += 1*(10**(n-1))
  
print(ans)

### FIXED CODE ###

# -*- coding:utf-8 -*-
n, m = map(int, input().strip().split())
ans = 0

digit ={}
for i in range(m):
    tmp_d, tmp = map(int, input().strip().split())
       	
    if (tmp_d in digit.keys()) and (digit[tmp_d] != tmp):
        print(-1)
        exit()
    else:
        digit[tmp_d] = tmp
      
      
if not (1 in digit.keys()) and n>=2:
	digit[1] = 1
    
ans = 0
for key in digit.keys():
  ans += digit[key]*(10**(n-key))

if len(str(ans)) == n: 
  print(ans)
else:
  print(-1)
n, m = map(int, input().split())
data = [[int(e) for e in input().split()] for _ in range(n)]
d1 = {}
for i in range(n):
  a, b = data[i]
  if a not in d1:
    d1[a] = []
  d1[a].append(b)
result = 0
d2 = {}
maxb = -1
for i in range(1, m + 1):
  if i in d1:
    for j in d1[i]:
      if j not in d2:
        d2[j] = 0
      d2[j] += 1
      if j > maxb:
        maxb = j
  else:
    if len(d2) == 0:
      continue
  result += maxb
  if d2[maxb] == 1:
    del d2[maxb]
    if len(d2) == 0:
      maxb = 0
    else:
      max(d2.keys())
  else:
    d2[maxb] -= 1
print(result)


### FIXED CODE ###

n, m = map(int, input().split())
d1 = {}
for _ in range(n):
  a, b = map(int, input().split())
  if a in d1:
    d1[a].append(b)
  else:
    d1[a] = [b]
result = 0
d2 = {}
maxb = -1
for i in range(1, m + 1):
  if i in d1:
    for j in d1[i]:
      if j not in d2:
        d2[j] = 0
      d2[j] += 1
      if j > maxb:
        maxb = j
  else:
    if len(d2) == 0:
      continue
  result += maxb
  if d2[maxb] == 1:
    del d2[maxb]
    if len(d2) == 0:
      maxb = 0
    else:
      maxb = max(d2.keys())
  else:
    d2[maxb] -= 1
print(result)
x=list(input())
n=len(x)

stack=[x[0]]
for i in range(1,n):
  if x[i]=='S':
    stack.append('S')
  else:
    if stack[-1]=='S':
      stack.pop()
    else:
      stack.append('T')
print(len(stack))

### FIXED CODE ###

x=list(input())
n=len(x)

stack=['T',x[0]]
for i in range(1,n):
  if x[i]=='S':
    stack.append('S')
  else:
    if stack[-1]=='S':
      stack.pop()
    else:
      stack.append('T')
print(len(stack)-1)
import itertools
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    need = []
    iranaiko = []
    for a in A:
    	if a >= K:
    		need.append(a)
    	elif a in need:
    		need.append(a) 
    	elif a in iranaiko:
    		pass
    	else:
    		z = 0
    		B = A[:]
    		B.remove(a)
    		fusoku = [K - i - 1 for i in range(a)]
    		for bi,b in enumerate(B):
    			if b >= K:
    				break
    		B = B[:bi + 1]
    		for i in range(1,len(B) + 1):
    			C = list(itertools.combinations(B,i))
    			for c in C:
    				if sum(c) in fusoku:
    					need.append(a)
    					z = 1
    					break
    			if z == 1:
    				break
    		if z == 0:
    			iranaiko.append(a)
    print(N - len(need))

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
need = []
iranaiko = []
for a in A:
	if a >= K:
		need.append(a)
	elif a in need:
		need.append(a) 
	elif a in iranaiko:
		pass
	else:
		z = 0
		B = A[:]
		B.remove(a)
		fusoku = [K - i - 1 for i in range(a)]
		for bi,b in enumerate(B):
			if b >= K:
				bi = bi - 1
				break
		B = B[:bi + 1]
		B.reverse()
		C = [0]
		for b in B:
			D = []
			for c in C:
				if b + c < K:
					if b + c in fusoku:
						z = 1
						need.append(a)
						break
					D.append(b + c)
				
			D.append(0)
			C = D[:]
			if z == 1:
				break
			
		if z == 0:
			iranaiko.append(a)

print(N - len(need))
n = int(input())
s = input()
str = s[1:]
a = 0
for i in str:
  if i == "E":
    a += 1
b = a

for i in range(len(n)):
  if str[i] == "w":
  	if str[i+1] == "E":
      continue
    else:
      a += 1 
  else:
    if str[i+1] == "E"
      a -= 1
      if b > a:
        a = b
    else:
      continue
      
print(b)
    

    

### FIXED CODE ###

n = int(input())
s = input()
ans = s[1:].count("E")
a = ans
for i in range(n-1):
  if s[i] == "W":
    a += 1
  if s[i+1] == "E":
    a -= 1
  if a < ans:
    ans = a
print(ans)
def QSortPosition(list,low,high):
    LsaveNum=list[low]
    pivotkey=list[low]
    while(low<high):
        while(list[low]<pivotkey) :
            low+=1
        list[high]=list[low]
        high-=1
        while(list[high]>pivotkey):
            high-=1
        list[low]=list[high]
        low+=1
    list[low]=LsaveNum
    return low

def QSort(list,s,t):
    if(s<t):
        pivotkey=QSortPosition(list,s,t)
        QSort(list,s,pivotkey-1)
        QSort(list,pivotkey+1,t)
    return list

def FindMinS(list,length):
	count1=0
	sum=0

	while count1<length:
		sum=sum+list[count1]
		count1+=1

	InvidNum=length-1
	location=0
	count2=0
	MinList=[]

	while count2<InvidNum:
		count3=count2
		ab1=0
		ab2=0
		while count3<=location:
			ab1=ab1+list[count3]
			count3+=1
			ab2=sum-ab1
			ab3=abs(ab2-ab1)
			MinList.append(ab3)
		count2+=1

	MinList=QSort(MinList,0,InvidNum-1)
	return MinList[0]

num=input("请输入列表长度：")
count=0
list=[]
while count<num:
	listele=input("输入元素：")
	list.append(listele)
	count+=1
minnum=FindMinS(list,num)
print(minnum)

### FIXED CODE ###

import sys

n = int(input())
a = []
b = input().split(" ")
for i in range(n):
	a.append(int(b[i]))

for i in range(1, n):
	a[i] += a[i-1]

mn = abs(a[n-1] - 2*a[0])
for i in range(1, n-1):
	mn = min(mn, abs(a[n-1] - 2*a[i]))

print(mn)
r,g,b=map(int, input().split())

if (r*100+g*10+b)%4==0:
    print("Yes")

else:
    prinnt('No')

### FIXED CODE ###

r, g, b = map(int, input().split())
if (g * 10 + b) % 4 == 0:
  print("YES")
else:
  print("NO")
import sys
input = sys.stdin.readline

ina = input()
if ina == "1":
  print("Hello World")
else:
  inb = int(input())
  inc = int(input())
  print(inb + inc)

### FIXED CODE ###

ina = input()
if ina == "1":
  print("Hello World")
else:
  inb = int(input())
  inc = int(input())
  print(inb + inc)
a, b = map(int, (input().split()))
print(a * b if a <= 9 and b <= 9 else -1).

### FIXED CODE ###

a, b = map(int, (input().split()))
print(a * b if a <= 9 and b <= 9 else -1)
import math
N, a, b = map(int,input().split())
p = 10 ** 9 +7
def fc(t):
  if t == 0:
    return 1
  elif t % 2 == 1:
    return ((fc(t//2)) **2 )* 2
  else:
    return (fc(t//2)) ** 2
A = math.factorial(a)
B = math.factorial(b)
n_c_a = 1
n_c_b = 1
for i in range(a):
  n_c_a *= n-i
for j in rnage(b):
  n_c_b *= n-j
m_a = (n_c_a // A)% p
m_b = (n_c_b // A) % p
print((fc(N) - 1 - m_a - m_b) % p)


### FIXED CODE ###

N, a, b = map(int,input().split())
p = pow(10,9) + 7
def comb(n,r):
  bunshi = 1
  for i in range(n-r+1, n+1):
    bunshi =bunshi * i % p
  bunbo = 1
  for i in range(1, r+1):
    bunbo = bunbo * i % p
  return bunshi * pow(bunbo, p-2, p)
print((pow(2,N, p) - 1 - comb(N,a) - comb(N,b)) % p)
import functools
import fractions

def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N = int(input())
    A = list(map(int, input().split()))
    A = list(set(A))
    N = len(A) + 1
  else:
    # N = 3
    # A = [7,6,8]
    # N = 3
    # A = [12,15,18]
    N = 2
    A = [1000000000,1000000000]

  x = 0
  for i in range(N):
    tmp = functools.reduce(fractions.gcd, A[0:i]+A[i+1:])
    if tmp > x:
      x = tmp
  
  print(x)
  
main()

### FIXED CODE ###

import functools
import fractions

def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N = int(input())
    A = list(map(int, input().split()))
  else:
    # N = 3
    # A = [7,6,8]
    N = 3
    A = [12,15,18]
    # N = 3
    # A = [1,1000000000,1000000000]

  AL = [0] * N    
  AR = [0] * N
  for i in range(N):
    if i != 0:
      AL[i] = fractions.gcd(AL[i-1],A[i])
    else:
      AL[i] = A[i]
    j = N - i - 1
    if j!= N - 1:
      AR[j] = fractions.gcd(AR[j+1],A[j])
    else:
      AR[j] = A[j]
      
  if 'get_ipython' in globals():   
    print(AL)
    print(AR)
  
  x = 0
  for i in range(N):
    if i == 0:
      tmp = AR[i+1]
    elif i == N - 1:
      tmp = AL[i-1]
    else:
      tmp = fractions.gcd(AL[i-1],AR[i+1])
    if tmp > x: x = tmp
  
  print(x)
    
main()
N=int(input())
A=[]
for n in range(N):
	A.append(input())
B=A.copy()
B.sort()
C=B[N-1]
D=B[N-2]
for i in range(N):
	if A[i]==C:
		print(D)
	else:
		print(C)
	


### FIXED CODE ###

import copy
N = int(input())
S = []
for i in range(N):
    S.append(int(input()))

B=copy.copy(S)
B.sort()
if N>2:
	C=int(B[N-1])
	D=int(B[N-2])
	for i in S:
		if int(i)>=C:
			print(D)
		else:
			print(C)

else:
	print(S[1])
	print(S[0])
S = str(input())
days = {"SUN":"7","MON":"6","TUE":"5","WED":"4","THU":"3","FRI":"2","SAT":"1"}
print(days(S))

### FIXED CODE ###

S = str(input())
days = {"SUN":"7","MON":"6","TUE":"5","WED":"4","THU":"3","FRI":"2","SAT":"1"}
print(days[S])
n,m=map(int,input().split())
A=list(map(int,input().split()))
for i in range(n):
    A[i]/=2
from fractions import gcd
kou=A[0]*A[1]/gcd(A[0],A[1])
for a in A:
    kou=a*kou/gcd(a,kou)
#print(kou)
ans=(m//kou+1)//2
print(int(ans))


### FIXED CODE ###

def main():
    """"ここに今までのコード"""
    import sys
    input = sys.stdin.readline
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    #A.sort()
    if n==1:
        ans=(m//(A[0]//2)+1)//2
        print(int(ans))
        exit()
    from fractions import gcd
    kou=A[0]*A[1]//gcd(A[0],A[1])
    for a in A:
        kou=a*kou//gcd(a,kou)
        if (kou//a)%2==0:
            print(0)
            exit()
    kou//=2
    #print(kou)
    ans=(m//kou+1)//2
    print(int(ans))
if __name__ == '__main__':
    main()
k, a, b = [int(i) for i in input().split()]
#k, a, b= 314159265, 35897932, 384626433

sum = 0
if a >= b:
    # A >= Bの場合
    # a,bに１施行ずつ使い、それ以外は叩く、という選択
    sum = k + 1
else:
    # A < B の場合
    diff = b - a
    if diff == 1:
        sum = k + 1
    elif diff == 2:
        sum = k + 1
    elif diff >= 3:
        # a->bコンボが利潤を生み続けるパターン
        rest = 1 + k - a
#         print("K:{}".format(rest))
        if rest >= 0:
            if rest % 2 == 0:
                sum = a + ((diff) * int(rest / 2))
#                 print("biscuits:{}".format(a))
#                 print("diff:{}, k/2:{}".format(diff, rest / 2))
            else:
                # 最後1回はコンボができないので、叩くパターン
                sum = a + ((diff) * int((rest - 1) / 2)) + 1
#                 print("biscuits:{}".format(a))
#                 print("diff:{}, k/2:{}".format(diff, (rest - 1) / 2))
        else:
            sum = k + 1
                
print(int(sum))


### FIXED CODE ###

k, a, b = [int(i) for i in input().split()]

sum = 0
if a >= b:
    # A >= Bの場合
    # a,bに１施行ずつ使い、それ以外は叩く、という選択
    sum = k + 1
else:
    # A < B の場合
    diff = b - a
    if diff == 1:
        sum = k + 1
    elif diff == 2:
        sum = k + 1
    elif diff >= 3:
        # a->bコンボが利潤を生み続けるパターン
        rest = 1 + k - a
#         print("K:{}".format(rest))
        if rest >= 0:
            if rest % 2 == 0:
                sum = a + ((diff) * int(rest / 2))
#                 print("biscuits:{}".format(a))
#                 print("diff:{}, k/2:{}".format(diff, rest / 2))
            else:
                # 最後1回はコンボができないので、叩くパターン
                sum = a + ((diff) * int((rest - 1) / 2)) + 1
#                 print("biscuits:{}".format(a))
#                 print("diff:{}, k/2:{}".format(diff, (rest - 1) / 2))
        else:
            sum = k + 1
                
print(int(sum))
li = list(map(int,input().split()))
A = li[0]
B = li[1]
C = li[2]
D = li[3]

if A * B > C * D:
  print(A * B)
elif A * B < C * D:
  print(C * D)
else
  print(A * B)

### FIXED CODE ###

li = list(map(int,input().split()))
A = li[0]
B = li[1]
C = li[2]
D = li[3]

if A * B > C * D:
  print(A * B)
elif A * B < C * D:
  print(C * D)
else:
  print(A * B)
input_number = input()
if input_number = 0:
  print(1)
else:
  print(0)

### FIXED CODE ###

a = int(input())
if a==1:
  print(0)
else:
  print(1)
n,m=map(int,input().split())

ac_cnt=[False]*n
wa_cnt=[0]*n

p=int(p-1)

for _ in range(m):
    a,b=input().split()
    if b == "AC":
        ac_cnt[a] == True
    else:
        if ac_cnt[a] == False:
            wa_cnt[a] += 1
a=0
b=0

for i in range(n):
    if ac_cnt[a]:
        a += 1
        b += wa_cnt[i]

print(a,b)

### FIXED CODE ###

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

ac_cnt=[False]*n
wa_cnt=[0]*n

for _ in range(m):
    a,b=input().split()
    a=int(a)-1
    if b == "AC":
        ac_cnt[a] = True
    else:
        if ac_cnt[a] == False:
            wa_cnt[a] += 1
c=0
d=0

for i in range(n):
    if ac_cnt[i]:
        c += 1
        d += wa_cnt[i]

print(c,d)
ls = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
num = input()
k = int(num) + 1
print(ls[k])

### FIXED CODE ###

ls = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
num = input()
print(ls[int(num)-1])
n,r = map(int,input().split())

if n >= 10:
  print(k)
else:
  print(r+100*(10-n))

### FIXED CODE ###

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

if n >= 10:
  print(r)
else:
  print(r+100*(10-n))
a,b=open(0);print([x:=eval(b.replace(*' *')),-1][x>10**18or len(b)>=99])

### FIXED CODE ###

a,b=open(0);c=1;
for i in sorted(b.split()):
    c*=int(i)
    if c>10**18:print(-1);exit()
print(c)
import functools
import math

N,X=map(int,input().split())

A=list(map(int,input().split()))
B=[]
for i in range(len(A)):
    B.append(A[i]-X)
#print(B)

gcd = functools.reduce(math.gcd, B)
print(gcd)

### FIXED CODE ###

N,X=map(int,input().split())
A=list(map(int,input().split()))
B=[]
for i in range(N):
    B.append(abs(A[i]-X))


a=B[0]

for j in range(1,N):
    b=B[j]
    if b<a:
        a,b=b,a
    while b!=0:
        a,b=b,a%b
print(a)
S = input()
T = input()
 
if S == T[:-1]
     print("YES")
  else:
  print("NO")

### FIXED CODE ###


    
s = input()
t = input()

if t[:-1] == s:
    print("Yes")
else:
    print("No")
D,N=map(int,input().split())
if N<100:
  F=100**D
  print(F*N)

else:
  print(F*101)

### FIXED CODE ###

D,N=map(int,input().split())
F=100**D
if N<100:
  print(F*N)

else:
  print(F*101)
N, K = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)

def check(i):
	if i == 0:
		b = a[1:]
	elif i == N - 1:
		b = a[:N - 1]
	else:
		b = a[:i] + a[i+1:]
	#print(b)
	ok = False
	dp = [[False] * K for _ in range(N - 1)]
	dp[0][b[0]] = True
	if K - a[i] <= b[0] < K:
		ok = True
	for j in range(1, N - 1):
		for k in range(1, K):
			if dp[j - 1][k] == True:
				dp[j][k] = True
			elif k > b[j]:
				if dp[j - 1][k - b[j]] == True:
					dp[j][k] = True

			if dp[j][k] == True and K - a[i] <= k < K:
				ok = True

	if ok:
		#del b, dp
		return True
	else:
		#del b, dp
		return False


def bi_search(lower, upper):
	#print(lower, upper)
	mid = (lower + upper) // 2
	#print(mid)
	if check(mid) == False and check(mid + 1) == True:
		#print("hoge")
		return mid + 1
	elif mid == 0 and check(mid) == True:
		return 0
	elif mid == N - 2 and check(mid + 1) == False:
		return N
	elif check(mid) == True:
		return bi_search(lower, mid)
	else:
		return bi_search(mid, upper)


print(bi_search(0, N - 1))

### FIXED CODE ###

import sys

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1

def check(mi):
    x = a[mi-1]
    if x >= k:
        return True
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        y = a[i]
        for j in range(k, -1, -1):
            if j >= y:
                dp[j] = dp[j] | dp[j-y]

    if sum(dp[k-x:k]):
        return True
    else:
        return False

if check(1):
    print(0)
    sys.exit()

if not check(n):
    print(n)
    sys.exit()

while ba-fr > 1:
    mi = (ba+fr+1) // 2
    if check(mi):
        ba = mi
    else:
        fr = mi

print(fr)
now = 0
before = -9999
answer = 1

for a in a_n:
    if a - before == 1:
        answer = 0
        break    
    answer *= Fib( a - 1 - now + 2 )
    answer %= 1000000007
    now = a + 1
    before = a

if answer > 0:
    answer *= Fib( N - now + 2)
    answer %= 1000000007

print(answer )

### FIXED CODE ###

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

m = sum(w)
b = m
answer = T
for t in range(1, T):
    k = sum(w[0:t+1])
    diff= abs(2*k - m) 
    if diff < b:
        b = diff 
    else:
        break
print(b)
A,B,H,M = map(int, input().split())
X = H / 12 * 360 + M / 60 * 30
Y = M / 60 * 360 

if X - Y => 0 and X - Y <= 180:
 C = X - Y
elif X - Y > 180:
 C = 360 - (X - Y)
elif X - Y <= 0 and X - Y > -180:
 C = Y - X
else:
 C = 360 - (Y - X)
print(math.sqrt(A*A + B*B - 2*A*B*math.cos(math.radians(int(C))) ))


### FIXED CODE ###

import math
A,B,H,M = map(int, input().split())
X = H*30+M*0.5
Y = M*6
if  -180 < X - Y < 0:
  z = Y - X
elif X - Y <= -180:
  z = 360 -(Y - X)
elif 180 > X - Y >= 0:
  z = X - Y
elif X - Y >= 180:
  z = 360-(X - Y)
ans = A*A+B*B-2*A*B*math.cos(math.radians(z))
ANS = math.sqrt(ans)

print(ANS)
# -*- coding: utf-8 -*-
a = int(input())

for i in range(a):
  lis = list(map(int, input().split()))
  judge = True
  if (lis[i] % 2 == 0):
    if (lis[i] % 3 != 0) and (lis[i] % 5 != 0):
      judge = False
# 出力
if judge:
  print("APPROVED")
else:
  print("DENIED")

### FIXED CODE ###

# -*- coding: utf-8 -*-
a = int(input())
lis = list(map(int, input().split()))
for i in range(a):
  judge = True
  if (lis[i] % 2 == 0):
    if (lis[i] % 3 != 0) and (lis[i] % 5 != 0):
      judge = False
      break
# 出力
if judge:
  print("APPROVED")
else:
  print("DENIED")
var=n;

cin>>n;

print(n*n*n)

### FIXED CODE ###

n = int(input())

print(n*n*n)
x,y = input().split()
print((x-1)*(y-1))

### FIXED CODE ###

x,y = map(int, input().split())
print((x-1)*(y-1))
a1,b1,a2,b2=map(int,input().split())

import sys
sys.setrecursionlimit(2000000000)

p = 10 ** 9 + 7
N = a2+b2+2  # N は必要分だけ用意する
R = a2+1
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
  fact.append((fact[-1] * i) % p)
  
for i in range(2, R + 1):
  inv.append((-inv[p % i] * (p // i)) % p)
  factinv.append((factinv[-1] * inv[-1]) % p)

def comb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fact[n] * factinv[r] * factinv[n-r] % p

score=comb(a2+b2+2,a2+1,p)-comb(a2+b1+1,a2+1,p)-comb(a1+b2+1,a1,p)+comb(a1+b1,a1,p)
print(score%(10**9+7))

### FIXED CODE ###

a1,b1,a2,b2=map(int,input().split())

import sys
sys.setrecursionlimit(2000000000)

p = 10 ** 9 + 7
N = a2+b2+2  # N は必要分だけ用意する
R = max(a2+1,b2+1)
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
  fact.append((fact[-1] * i) % p)
  
for i in range(2, R + 1):
  inv.append((-inv[p % i] * (p // i)) % p)
  factinv.append((factinv[-1] * inv[-1]) % p)

def comb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fact[n] * factinv[r] * factinv[n-r] % p

score=comb(a2+b2+2,a2+1,p)-comb(a2+b1+1,a2+1,p)-comb(a1+b2+1,a1,p)+comb(a1+b1,a1,p)
print(score%(10**9+7))