Harryxun/stf_run huggingface dataset:
N = int(input())+1
ali = list(map(int,input().split()))
nli = [0]*N

maxn = 2**(N-1)
nli[-1] = ali[-1]

for i in range(1,N+1):
  nli[-i] = min(maxn,nli[-i+1] + ali[-i])
  maxn //= 2
  

ulim = 1
for i in range(N):
  nli[i] = min(nli[i],ulim)
  ulim = (ulim - ali[i])*2
  if i != N-1 and ulim <= 0:
    print(-1)
    print(nli[N+1])
    exit()
  
print(sum(nli))

### FIXED CODE ###

N = int(input())+1
ali = list(map(int,input().split()))
nli = [0]*N

maxn = 2**(N-1)
nli[-1] = ali[-1]

for i in range(1,N+1):
  nli[-i] = min(maxn,nli[-i+1] + ali[-i])
  maxn //= 2
  

ulim = 1
for i in range(N):
  nli[i] = min(nli[i],ulim)
  ulim = (ulim - ali[i])*2
  if ulim < 0:
    print(-1)
    exit()
  
print(sum(nli))
N = int(input())
XY = [list(map(int,input().split())) for _ in range(N)]
def gdb(a,b):
    a,b = abs(a),abs(b)
    while b:
        a,b = b,a%b
    return a
def make_slope(a,b):
    if a==0:
        print("error")
    elif a>0:
        return(a//gdb(a,b),b//gdb(a,b))
    elif a<0:
        return(-1*a//gdb(a,b),-1*b//gdb(a,b))


slope_list = []
for i in range(1,N):
    for j in range(i):
        x1,y1 = XY[i]
        x2,y2 = XY[j]
        d_x = x2-x1
        d_y = y2-y1
        if d_x != 0:
            d_x,d_y = make_slope(d_x,d_y)
            if not([d_x,d_y] in slope_list):
                slope_list.append([d_x,d_y])

if N <= 2:
    print(1)
else:
    tmp = []
    for x,y in XY:
        if not (x in tmp):
            tmp.append(x)
    ans = len(tmp)

    for d_x,d_y in slope_list:
        XY_list = []
        for x1,y1 in XY:
            if XY_list == []:
                XY_list.append([x1,y1])
            else:
                for x2,y2 in XY_list:
                    d_x_tmp = x2-x1
                    d_y_tmp = y2-y1
                    if d_x_tmp == 0:
                        break
                    d_x_tmp,d_y_tmp = make_slope(d_x_tmp,d_y_tmp)
                    if d_x_tmp==d_x and d_y_tmp==d_y:
                        break
                else:
                    XY_list.append([x1,y1])
        ans = min(ans,len(XY_list))
    print(ans)


### FIXED CODE ###

N,K = map(int,input().split())
if K==1:
    print(0)
else:          
    print(N-K)
N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [10**9+5] * N
dp[0] = 0
for i in range(1, N):
    for j in range(1, min(i, K)+1):
        dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j])
print(dp[N-1])

### FIXED CODE ###

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

dp = [1e10] * N
dp[0] = 0
for i in range(N):
    for j in range(i+1, i+K+1):
        if j >= N:
            break
        dp[j] = min([dp[j], dp[i]+abs(h[j]-h[i])])
print(dp[N-1])
N,X =[int(i) for i in input().split()]
c = [int(i) for i in input().split()]

c.append(X)
c.sort()

index_x = c.index(X)

if len(c) == 2:
    print(abs(c[index_x] - c[index_x - 1]))
else:
    print(min(c[index_x] - c[index_x - 1],c[index_x + 1] - c[index_x]))

### FIXED CODE ###

import fractions
from functools import reduce

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

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


N,X =[int(i) for i in input().split()]
c = [int(i) for i in input().split()]

for i in range(N):
    c[i] = abs(c[i] - X)

print(gcd_list(c))
N,M = list(map(int, input().split()))
X = list(map(int, input().split()))

X.sort()
cnt = 0
arr = [0]*(M-1)
if N > M:
    ans = 0
else:
    for i in range(1,M):
        arr[i] = (abs(X[i-1]-X[i]))
    #print(arr)
    arr.sort()
    ans = sum(arr[0:M-N])
print(ans)

### FIXED CODE ###


def solve():
    if N >= M:
        return 0
    elif N == 1:
        cnt = abs(X[-1] - X[0])
        return cnt
    L = [0] * (M-1)
    
    for i in range(len(L)):
        L[i] = X[i+1] - X[i]
    L.sort()
    return sum(L[:M-N])



if __name__=="__main__":
    N,M = list(map(int, input().split()))
    X = list(map(int, input().split()))
    X.sort()
    print(solve())
a,b,k=map(int, input().split()) 
if a>=k:
  print(a-k,b)
else:
  print(0,max(a-k+b, 0))

### FIXED CODE ###

s, t = input().split()

print(t+s)
text = input()
if text == "RRS":
    print(2)
elif text == "SSS":
    print(0)
else text == "RSR":
    print(1)

### FIXED CODE ###

a = input()

if a == "RSR":
    print(1)
else :
    print(a.count("R"))
# スペース区切りの整数の入力
N,M = map(int, input().split())
A_list=[]
food_list=[]

for i in range(N):
  A_list.append([int(e) for e in input().split()])

for i in range(M):
  food_list.append(0)
  
for i in range(N):
  K=A_list[i][0]
  for j in range(1,K+1):
    #print(A_list[i][j],end="")
    food_list[A_list[i][j]-1]+=1

ans=0
    
for i in range(M):
  if food_list[i]==N:
    ans+=1
    
print(ans)

### FIXED CODE ###

# スペース区切りの整数の入力
A,B = map(int, input().split())

if B%A==0:
  print(A+B)
else:
  print(B-A)
import fractions
n = int(input())
a = list(map(int, input().split()))

left = []
left.append(a[0])
right = []
right.append(a[n-1])
for i in range(n-2):
	right.append(fractions.gcd(right[i], a[n-2-i]))

for i in range(n):
	if i == 0:
		ma = right[n-2]
	elif i == n-1:
		if ma < left[n-2]:
			ma = left[n-2]
	elif ma < math.gcd(left[i-1], right[n-2-i]):
		ma = fractions.gcd(left[i-1], right[n-2-i])
		left.append(fractions.gcd(left[i-1], a[i]))

print(ma)

### FIXED CODE ###

import fractions
n = int(input())
a = list(map(int, input().split()))

left = []
left.append(a[0])
right = []
right.append(a[n-1])
for i in range(n-2):
	right.append(fractions.gcd(right[i], a[n-2-i]))

for i in range(n):
	if i == 0:
		ma = right[n-2]
	elif i == n-1:
		if ma < left[n-2]:
			ma = left[n-2]
	else:
		gc = fractions.gcd(left[i-1], right[n-2-i])
		if ma < gc:
			ma = gc
		left.append(fractions.gcd(left[i-1], a[i]))

print(ma)
def moov(x,y):
    if (x,y) in Loc:
        return "LOOP"
    else:
        Loc.append((x,y))
        if Room[y][x] == ".":
            return str(x)+" "+str(y)
        elif Room[y][x] == ">":
            return moov(x + 1,y)
        elif Room[y][x] == "<":
            return moov(x - 1,y)
        elif Room[y][x] == "^":
            return moov(x,y - 1)
        elif Room[y][x] == "v":
            return moov(x,y + 1)
    

while True:
    Loc = []
    Room = []
    h,w = map(int,input().split())
    if h == w == 0:
        break
    for i in range(h):
        vec = input()
        Room.append(list(vec))
    print(moov(1,0))

### FIXED CODE ###

def move(Tiles_map, x, y, Loop_ch):
    if [x,y] in Loop_ch:
        print("LOOP")
        return
    else:
        Loop_ch.append([x,y])

    if Tile_map[x][y] == ".":
        print(str(y) + " " + str(x))
        return
    elif Tile_map[x][y] == ">":
        move(Tiles_map, x, y+1, Loop_ch)
    elif Tile_map[x][y] == "<":
        move(Tiles_map, x, y-1, Loop_ch)
    elif Tile_map[x][y] == "v":
        move(Tiles_map, x+1, y, Loop_ch)
    elif Tile_map[x][y] == "^":
        move(Tiles_map, x-1, y, Loop_ch)

        
        
while True:
    Tile_map = []
    Loop_ch = []
    H, W = map(int,input().split())
    if H == 0 and W == 0:
        break
    for i in range(H):
        Tiles = input()
        Tiles = list(str(Tiles))
        Tile_map.append(Tiles)
    ans = move(Tile_map,0,0,Loop_ch)
hp, _ = map(int, input().split(" "))
s = sum(map(int, input().split(" ")))
return (hp - s) <= 0

### FIXED CODE ###

hp, _ = map(int, input().split(" "))
s = sum(map(int, input().split(" ")))
print("Yes" if (hp - s) <= 0 else "No")
n,m=(int(i) for i  in input().split())
#print(n,m)
mtrx=[[int(i)-1 for i in input().split()] for j in range(m)]
#print(mtrx)
adjacent=[[i] for i in range(n)]
#print(adjacent)
for i in range(n):
    adjacent[mtrx[i][0]]+=[mtrx[i][1]]
    adjacent[mtrx[i][1]]+=[mtrx[i][0]]
#print(adjacent)

cnt=[]
def dfs(goal,path):
    p=path[-1]
    if p==goal:
        cnt.append(len(set(path)))
        return
    else:
        for x in adjacent[p]:
            if x in path:
                continue
            else:
                path.append(x)
                dfs(goal,path)
                path.pop()

for i in range(1,n):
    dfs(i,[0])                

print(cnt.count(n))


### FIXED CODE ###

n,m=(int(i) for i in input().split())
mtrx=[[int(i) for i in input().split()] for j in range(m)]
#print(mtrx)
mtrx+=[[mtrx[i][1],mtrx[i][0]] for i in range(m)]
#print(mtrx)
mylist=[10*mtrx[i][0]+mtrx[i][1] for i in range(len(mtrx))]
#print(mylist)
# 順列を格納するリスト
perm = []
cnt=[]
# 順列の生成
def make_perm(n, m = 0):
    if n == m and perm[0]==1:
        flag=1
        for i in range(len(perm)-1):
            myval=10*perm[i]+perm[i+1]
            myval1=mylist.count(myval)
            flag=flag*myval1
        cnt.append(flag)
        
    else:
        for x in range(1, n + 1):
            if x in perm: continue
            perm.append(x)
            make_perm(n, m + 1)
            perm.pop()
            
make_perm(n)
print(sum(cnt))
import math

A,B=map(int,(input().split()))    
ABgcd=math.gcd(A,B)
answer=A*B//ABgcd
print(answer)

### FIXED CODE ###

one_two_three=[1,2,3]
a=int(input())
b=int(input())
one_two_three.remove(a)
one_two_three.remove(b)
print(one_two_three[0])
a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())

delta_t = abs(a - b)/abs(v - w) - 1
print(delta_t)

if v <= w:
    print("No")
elif t < delta_t:
    print("No")
else:
    print("Yes")


### FIXED CODE ###

a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())

if v <= w:
    print("NO")
elif t < abs(a - b) / abs(v - w):
    print("NO")
else:
    print("YES")
def resolve():
    N = int(input())
    x, y, = [], []
    for i in range(N):
        x_tmp, y_tmp = list(map(int, input().split()))
        x.append(x_tmp)
        y.append(y_tmp)
    ans = 0
    ls = list(permutations(list(range(N)), N))
    for l in ls:
        for i in range(len(l)-1):
            ans += dist(x[l[i]], y[l[i]], x[l[i+1]], y[l[i+1]])

    print(ans / len(ls))
    return

resolve()

### FIXED CODE ###

import math
from itertools import permutations

def dist(x0, y0, x1, y1):
    return math.sqrt((x0 - x1) ** 2 + (y0 - y1) ** 2)

def resolve():
    N = int(input())
    x, y = [], []
    for _ in range(N):
        x_tmp, y_tmp = list(map(int, input().split()))
        x.append(x_tmp)
        y.append(y_tmp)

    ls = list(permutations(list(range(N)), N))
    ans = 0
    for l in ls:
        idx = 0
        while idx + 1 < len(l):
            ans += dist(x[l[idx]], y[l[idx]], x[l[idx+1]], y[l[idx+1]])
            idx += 1

    print(ans / len(ls))
    return

resolve()
import re

N, S = map(int, input().split(' '))
pattern = "AC+"
T = input()
for _ in range(S):
    fir,fin = map(int, input().split(' '))
    result = re.findall(pattern, T[fir -1:fin])
    print(len(result))

### FIXED CODE ###

dic = {'A': 'T', 'T': 'A', 'C': 'G', 'G': 'C'}
b = input()
print(dic[b])
import copy
A, B, C, K = map(int, input().split())
maxL = 10 ** 18
L = [A, B, C]
for i in xrange(K):
    newL = [L[1] + L[2], L[0] + L[2], L[0] + L[1]]
    L = copy.copy(newL)

ans = L[0] - L[1]
if ans >= maxL:
    print("Unfair")
else:
    print(ans)

### FIXED CODE ###

A, B, C, K = map(int, input().split())
maxL = 10 ** 18
L = [A, B, C]
ans = A - B
if ans >= maxL:
    print("Unfair")
else:
    if K % 2 == 0:
        print(ans)
    else:
        print(ans * (-1))
n=int(input())
x,y=[int(input()) for _ in range(int(input()))],[int(input()) for _ in range(int(input()))]
d=0
for i,j in zip(x,y):
  for k,l in zip(x,y):
    m1,m2=i-k,j-l
    o=m1**2+m2**2
    d+=o**0.5
print(d/n)

### FIXED CODE ###

n=int(input())
x=[0]*n
y=[0]*n
for i in range(n):
  x[i],y[i]=map(int, input().split())
d=0
for i,j in zip(x,y):
  for k,l in zip(x,y):
    m1,m2=i-k,j-l
    o=m1**2+m2**2
    d+=o**0.5
print(d/n)
ini = int(input().split(" ")[0])
negaset = [int(x) for x in input().split(" ")]
okset = sorted([str(i) for i in range (10) if i not in negaset]) 
#print(ini,okset)

for p in itertools.product(okset,repeat = 5):
    stp = int("".join(p))
    if stp >= ini:
        print(stp)
        break

### FIXED CODE ###

# coding: utf-8
# Here your code !
ipt = input().split(" ")
j,k =0,0
for i in [ int(i) for i in ipt]:
    if i == 5:
        k += 1
    elif i==7:
        j += 1
#    print(ipt,i,k,j)

if j == 1 and k == 2:
    print("YES")
else:
    print("NO")
import sys

N = int(input())
nums = list(map(int, input().split(' ')))

output = 1

if 0 in nums:
  print(0)
  sys.exit()
  
else:
  for x in nums:
    output *= x

    if output > 10**18:
      print(-1)
      sys.exit()

  print(output)

### FIXED CODE ###

N, M = input().split(' ')
N, M = int(N), int(M)

print(N*M)
s = input().split()
print(int((s[0])+(int(s[1]))/2))

### FIXED CODE ###

s = input().split()
N = int(s[0])
W = int(s[1])/2
print(int(N+W))
N, K = map(int, input().split())
N, K = map(abs, (N,K))
amari = N%K
if amari == 0:
    print(0)
else:
    amari2 = K - amari
    print(max(amari, amari2)

### FIXED CODE ###

N, K = map(int, input().split())
N, K = map(abs, (N,K))
amari = N%K
if amari == 0:
    print(0)
else:
    amari2 = K - amari
    print(min(amari, amari2))
from itertools import product
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
visited = []

def dfs(p):
    if p in visited or s[p[0]][p[1]] == '.':
        return None

    temp = [1 if s[p[0]+x][p[1]+y] == '#' else 0 for (y, x) in [[1, 0], [0, 1], [0, -1], [-1, 0]]
            if 0 <= x+p[0] < len(s[0]) and 0 <= y+p[1] < len(s)]
    if sum(temp) <= 0:
        print('No')
        exit(0)


for i in range(len(s)):
    for j in range(len(s[0])):
        dfs([j, i])
print('Yes')


### FIXED CODE ###

from itertools import product

h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
visited = []

def dfs(p):
    if s[p[0]][p[1]] == '.':  # p[0]gatate , p[1] gayoko
        return None

    temp = [1 if s[p[0]+y][p[1]+x] == '#' else 0 for (x, y) in [[1, 0], [0, 1], [0, -1], [-1, 0]] if 0 <= y+p[0] < h and 0 <= x+p[1] < w]
    if sum(temp) <= 0:
        print('No')
        exit(0)


for i in range(len(s)):
    for j in range(len(s[0])):
        dfs([i, j])
print('Yes')
N=list(input())

n=reversed(N)

if n[0]=="2" or n[0]=="4" or n[0]=="5" or n[0]=="7" or n[0]=="9":
    print("hon")
elif n[0]=="0" or n[0]=="1" or n[0]=="6" or n[0]=="8":
    print("pon")
else:
    n[0]=="3":
    print("bon")
    break


### FIXED CODE ###

n=list(input())

n==n.reverse()

if (n[0]=="2" or n[0]=="4" or n[0]=="5" or n[0]=="7" or n[0]=="9"):
    print("hon")
elif (n[0]=="0" or n[0]=="1" or n[0]=="6" or n[0]=="8"):
    print("pon")
elif (n[0]=="3"):
    print("bon")
A = input()
B = input()
for a in range(len(A)):
  k=A[a:len(A)]+A[:a]
  if k == B:
    t = True
    break;
    
if t:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

A = input()
B = input()
t = False
for a in range(len(A)):
  k=A[a:len(A)]+A[:a]
  if k == B:
    t = True
    break;
    
if t:
  print('Yes')
else:
  print('No')
"""
dp[i] : 足場iに到達するにあたって、たどり着く最小回数
"""
INF = 10**10
dp = [INF]*11000
N = int(input())
hs  = list(map(int, input().split())) + [INF,INF]
dp[0] = 0
for i in range(N):
    dp[i+1] = min(dp[i+1], dp[i]+abs(hs[i+1]-hs[i]))
    dp[i+2] = min(dp[i+2], dp[i]+abs(hs[i+2]-hs[i]))
print(dp[N-1])

      

### FIXED CODE ###

import numpy as np
N = int(input())
hs = [int(i) for i in input().split()]
dp = np.zeros(N)
for i,h in enumerate(hs):
    if i == 0:        
        # 0は初期化されている
        dp[i] = 0
        continue
    elif i == 1:
        # 1は1通りしか無い
        dp[i] = dp[i-1] + abs(hs[i-1]-h)
    else:
        # 1個前か2個前で、コストが最小になるやつ
        dp[i] = min(dp[i-1]+abs(hs[i-1]-h),dp[i-2]+abs(hs[i-2]-h))
# print(dp)
print(int(dp[-1]))
a,b,c = map(int, input().split())
if a % 2 == 1 and b % 2 == 1:
	print("Yes")
else:
	print("No")


### FIXED CODE ###

a,b = map(int, input().split())
if a % 2 == 1 and b % 2 == 1:
	print('Yes')
else:
	print('No')
import math
# a: 時
# b: 分
# 
a, b, h, m = map(int, input().split())


x = ( a**2 + b**2 - 2*a*b* math.cos(int(360 / h) * 30) - int(360 / m) * 6 ) ** 0.5
print(x)


### FIXED CODE ###

import math
# a: 時
# b: 分
# 
a, b, h, m = map(int, input().split())

angle_h = h * 30 + m * 0.5
angle_m = m * 6

cos_ = math.cos( math.radians( abs( angle_h - angle_m ) ) )

x = ( a**2 + b**2 - 2*a*b*cos_ ) ** 0.5

print(x)
num = int(input())
li = list(input())
i = int(num/2)
while(i>num/2):
  fi = set(li[:i])
  se = set(li[i:])
  ans = len(list(fi & se))
  if i < ans:
    i = ans
  else:
    i = i+1    
 
print(i)

### FIXED CODE ###

li = list(map(int,input().split()))
ans = [li[0]+li[1],li[0]-li[1],li[0]*li[1]]
ans.sort()
print(ans[2])
N,M,C=map(int,input().split()) 
B=list(map(int,input().split()))
A =[list(map(int,input().split()))for i in range(N)]
ans=0
for i in range(N):
    for j in range(M):
        X+=(A[i][j]*B[j])
    X=X+C
    if  0 < X:
        ans = ans+1
print(ans)
    

### FIXED CODE ###

n,m,c=map(int,input().split())
B=list(map(int,input().split()))
A=[list(map(int,input().split()))for i in range(n)]
cnt=0
for i in range(n):
    total=0
    for j in range(m):
        total+=B[j]*A[i][j]
    total+=c
    if 0<total:
        cnt+=1
print(cnt)
n=int(input())
a=map(int,input().split())
ans=0
while i in a:
  while s in a:
    x=abs(s-i)
    if x>ans:
      ans=x
print(ans)

### FIXED CODE ###

n=int(input())
a=sorted(map(int,input().split()))
print(a[-1]-a[0])
b=input()
if b==A:
    print(T)
if b==T:
    print(A)
if b==G:
    print(C)
if b==C:
    print(G)


### FIXED CODE ###

b=input()
if b=='A':
    print('T')
if b=='T':
    print('A')
if b=='G':
    print('C')
if b=='C':
    print('G')
import math

def nPr(n, r):
    return math.factorial(n) // math.factorial(n - r)



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

ab = []
dic = {}
ans = 1

for i in range(N-1):

    a,b = map(int,input().split())
    ab.append([a,b])


while True:

    #print (ab)

    dic = {}

    if len(ab) == 0:
        ans *= K
        break
    elif len(ab) == 1:
        ans *= K * (K-1)
        break

    for i in ab:
        
        if i[0] in dic:
            dic[i[0]].append(i[1])
        
        else:
            dic[i[0]] = [i[1]]

        if i[1] in dic:
            dic[i[1]].append(i[0])
        
        else:
            dic[i[1]] = [i[0]]

    
    miki = []
    lma = 0
    for i in dic:

        lma = max(len(dic[i]),lma)
        if len(dic[i])>=2:
            miki.append(i)

    if lma >= K:
        ans = 0
        break

    for i in miki:

        lin_mik = 0
        for j in dic[i]:

            if j in miki:
                lin_mik += 1

        ans *= nPr( K - (1 + lin_mik) , len(dic[i])-lin_mik )
        #print (i,"のまわりは",nPr( K - (1 + lin_mik) , len(dic[i])-lin_mik ),"とおり")

    nab = []
    for i in ab:

        if (i[0] in miki) and (i[1] in miki):

            nab.append(i)

    ab = nab.copy()
    #print (miki,"みき",ans)

print (ans % (1000000007))

### FIXED CODE ###

from collections import deque
import sys

#modの掛け算

def modmal(a,b,mod): #a*bをmodを法にして求める

    return a * b % mod


#modの割り算

def moddiv(a,b,mod): #a/bをmodを法にして求める

    return (a * pow(b,mod-2,mod)) % mod


#逆元

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)



#modのn!と、n!の逆元を格納したリストを返す(拾いもの)
#factorialsには[1, 1!%mod , 2!%mod , 6!%mod… , n!%mod] が入っている
#invsには↑の逆元が入っている

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)

    return fac[n] * inv[n-r] * inv[r] % mod



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

mod = 10**9+7
fac,inv = modfac(max(N,K)+100 , mod)

dic = {}

for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

    dic[a].append(b)
    dic[b].append(a)

ans = K

for i in dic:

    if i == 0:

        ans *= fac[K-1] * inv[K-len(dic[i])-1]
        ans %= mod

        if len(dic[i]) >= K:
            print (0)
            sys.exit()

    else:

        ans *= fac[K-2] * inv[K-len(dic[i])-1]
        ans %= mod

        if len(dic[i]) >= K:
            print (0)
            sys.exit()

print (ans)
while True:
    try:
        n = int(raw_input())                                                                                                                                                                                 

        print (a**2+a+2)/2

    except EOFError: break

### FIXED CODE ###

while True:
    try:
        a = int(raw_input())                                                                                                                                                                                 

        print (a**2+a+2)/2

    except EOFError: break
h,w=map(int,input().split())
a=[]
for i in range(h):
    a.append(list(map(int,input().split())))

ans=[]
for i in range(h):
    for j in range(w):
        if(j==w-1 and i!=h-1 and a[i][j]%2!=0):
            a[i][j]-=1
            a[i+1][j]+=1
            ans.append([i,j,i+1,j])
        elif(a[i][j]%2!=0):
            a[i][j]-=1
            a[i][j+1]+=1
            ans.append([i,j,i,j+1])

print(len(ans))
for i in range(len(ans)):
    print(*ans[i])


### FIXED CODE ###

h,w=map(int,input().split())
a=[]
used=[[False for _ in range(w)] for _ in range(h)]
ans=[]
for i in range(h):
    ai=list(map(int,input().split()))
    for j in range(w):
        if(ai[j]%2!=0):
            if(j<w-1 and ai[j]>0 and ai[j]%2!=0 and not used[i][j]):
                used[i][j]=True
                ai[j]-=1
                ai[j+1]+=1
                ans.append([i+1,j+1,i+1,j+2])
    a.append(ai)

for i in range(h):
    if(i<h-1 and a[i][w-1]>0 and a[i][w-1]%2!=0 and not used[i][w-1]):
        used[i][w-1]=True
        a[i][w-1]-=1
        a[i+1][w-1]+=1
        ans.append([i+1,w,i+2,w])

print(len(ans))
for i in range(len(ans)):
    print(*ans[i])
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline

s=input().rstrip()
t="keyence"
i,j=0,0
while len(s)>i:
    if s[i]==t[j]:
        j+=1
    i+=1
print("YES"if j==7 else "NO")

### FIXED CODE ###

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

s=input().rstrip()
n=len(s)
t="keyence"
for i in range(n):
    for j in range(i,n):
        if s[:i]+s[j:]==t:
            print("YES")
            exit()
print("NO")
import itertools
L = input()
s = ['+','-']
t = ['+','-']
u = ['+','-']
for a, b, c in itertools.product(s, t, u):
   f = L[0] + a + L[1] + b + L[2] + c + L[3] 
   if eval(f) == 7:
       print(f+'=7')
       exit(0)


### FIXED CODE ###

N, Y = map(int, input().split(" "))
for i in range(N+1):
  for j in range(N+1-i):
    k = N-i-j
    if Y == (10000*k + 5000*j + 1000*i):
      print(k,j,i)
      exit(0)
print('-1 -1 -1')
input = input()
a,b=(int,input.split())
print("{0} {1} {2:.8}".format{a // b, a % b, a / b))



### FIXED CODE ###

a,b = map(int,input().split())
print("{0} {1} {2:.8f}".format(a // b, a % b, a / b))