Harryxun/stf_run huggingface dataset:
n, m = map(int, input().split())
mod = 10**9+7
facs = [1] * n
invs = [1] * n
nfac = 1
for i in range(1, n-m+1):
    nfac = nfac * i % mod
    facs[i] = nfac
    invs[i] = pow(facs[i], mod-2, mod)

ans = 1
start = 0
def steps(start, end):
    t = end - start
    pat = 0
    for j in range(t//2+1):
        pat += (facs[t-j] * invs[j] * invs[t-j-j]) % mod
    return pat%mod

for i in range(m):
    a = int(input())
    end = a-1
    if start == end+1:
        print(0)
        break
    # startからendまで行く方法
    ans *= steps(start, end)
    ans %= mod
    start = a+1
else:
    ans *= steps(start, n)
    ans %= mod
    print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
mod = 10**9+7
facs = [1] * (n-m+1)
invs = [1] * (n-m+1)
nfac = 1
for i in range(1, n-m+1):
    nfac = nfac * i % mod
    facs[i] = nfac
    invs[i] = pow(facs[i], mod-2, mod)

ans = 1
start = 0
def steps(start, end):
    t = end - start
    pat = 0
    for j in range(t//2+1):
        pat += (facs[t-j] * invs[j] * invs[t-j-j]) % mod
    return pat%mod

for i in range(m):
    a = int(input())
    end = a-1
    if start == end+1:
        print(0)
        break
    # startからendまで行く方法
    ans *= steps(start, end)
    ans %= mod
    start = a+1
else:
    ans *= steps(start, n)
    ans %= mod
    print(ans)
a=input()
k=0
while a[k]=='1'and len(a)>k:
  k+=1
b=int(input())
if b<k or a=='1'*len(a):print(1)
else:print(a[k])

### FIXED CODE ###

a=input()
b=int(input())
if b<101:
  if a[:b]=='1'*b:print(1)
  else:
    k=0
    while a[k]=='1':k+=1
    print(a[k])
else:
  k=0
  while a[k]=='1':k+=1
  print(a[k])
r=input()
if r<1200:
  print('ABC')
elif 1200<=r and r<2800:
  print('ARC')
else:
  print('AGC')

### FIXED CODE ###

r=int(input())
if r<1200:
  print('ABC')
elif 1200<=r and r<2800:
  print('ARC')
else:
  print('AGC')
print sum(map(int, raw_input().split())) < 10 else 'error'

### FIXED CODE ###

a,b= map(int, raw_input().split())
print a+b if (a+b < 10) else 'error'
N,K = map(int,input().split())
A = list(map(int,input().split()))
town = [[] for _ in range(N)]
visited = [0]

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

def teleport(i,con):
  goal = town[i][1]
  if goal in visited or con == N:
    return goal
  else:
    visited.append(goal)
    return teleport(goal,con + 1)

l = teleport(visited[0],0)

cs = visited.index(l)
cycle = visited[cs:]

if K < len(visited):
  print(visited[K] + 1)
else:
  K = K - len(visited) + len(cycle)
  print(cycle[K % len(cycle)] + 1)

### FIXED CODE ###

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

A = list(map(int,input().split()))
town = [[] for _ in range(N)]
visited = [0]
flag = [-1] * N

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

f = 0

while flag[f] == -1:
  t = town[f][1]
  flag[f] = t
  f = town[t][0]
  visited.append(t)
  
l = visited[-1]
lv = len(visited)

if K <= lv:
  print(visited[K] + 1)
else:
  cs = visited.index(l)
  cycle = visited[cs:-1]
  lc = len(cycle)
  print(cycle[(K - lv + 1) % lc] + 1)
##i
N=raw_input()
up=raw_input().split()

up=up.sort()
count=0
for i in range(N):
    count+=int(up[i*2])
print count

### FIXED CODE ###

N=raw_input()
up=raw_input()
up=up.split()

up=map(int,up)
up.sort()
count=0
for i in range(int(N)):
    count+=up[i*2]
print count
S = input()
K = int(input())

prev_c = S[0]
num_changes = 0
for c in S[1:]:
    if c == prev_c:
        num_changes += 1
        prev_c = 'replaced'
    else:
        prev_c = c

total_changes = 0
if S[0] == prev_c and S[1] == S[0] and len(S) % 2 == 1:
    num_changes2 = 0
    for c in S:
        if c == prev_c:
            num_changes2 += 1
            prev_c = 'replaced'
        else:
            prev_c = c
    total_changes = num_changes * int(K/2 + 1) + num_changes2 * int(K/2)
elif S[0] == prev_c:
    num_changes2 = 0
    for c in S:
        if c == prev_c:
            num_changes2 += 1
            prev_c = 'replaced'
        else:
            prev_c = c
    total_changes = num_changes + num_changes2 * (K-1)
else:
    total_changes = num_changes * K

print(total_changes)


### FIXED CODE ###

S = input()
K = int(input())

prev_c = S[0]
num_changes = 0
for c in S[1:]:
    if c == prev_c:
        num_changes += 1
        prev_c = 'replaced'
    else:
        prev_c = c

total_changes = 0
if len(S) == 1:
    if len(S) % 2 == 0:
        total_changes = int(K/2)
    else:
        total_changes = int((K-1)/2)
elif S[0] == prev_c and S[1] == S[0] and len(S) % 2 == 1:
    num_changes2 = 0
    for c in S:
        if c == prev_c:
            num_changes2 += 1
            prev_c = 'replaced'
        else:
            prev_c = c
    total_changes = num_changes * int(K/2 + 1) + num_changes2 * int(K/2)
elif S[0] == prev_c:
    num_changes2 = 0
    for c in S:
        if c == prev_c:
            num_changes2 += 1
            prev_c = 'replaced'
        else:
            prev_c = c
    total_changes = num_changes + num_changes2 * (K-1)
else:
    total_changes = num_changes * K

print(total_changes)
N, K, X, Y = map(int, input().split())
print(K*X + (N-K)*Y)

### FIXED CODE ###

N = int(input())
K = int(input())
X = int(input())
Y = int(input())
if N >= K:
    print(K*X + (N-K)*Y)
else:
    print(N*X)
N = map(int,input().split())
W = list(map(int,input().split()))
 
min_list = []
for i in range(N):
    mi = abs(sum(W[0:i]) - sum(W[i:]))
    min_list.append(mi)
print(min(min_list))

### FIXED CODE ###

n = int(input())
w = list(map(int, input().split()))
 
min_diff = 1000
for i in range(n):
	diff = abs(sum(w[0:i]) - sum(w[i:]))
	if diff < min_diff:
		min_diff = diff
print(min_diff)
a = int(input('<< '))
k=0
for i in range(1,a):
  if i%2 == 1:
    k += 1
  v = k/a

print v
   
    


### FIXED CODE ###

a = int(input())
if a%2 == 0:
  print(1/2)
else:
  print((a//2+1)/a)
x = input().split()[1]
ans = 0
 
a = input().split()
a.sort()
 
for i in len(a):
  if a[i] > x:
    print(ans)
    break
  else:
    x-=a[i]
    if i!=len(a)-1:
      ans+=1
    else:
      if a[i]==x:
        ans+=1
      print(ans)

### FIXED CODE ###

line = input().split()
N = int(line[0])
x = int(line[1])
ans = 0

a = input().split()
a = [int(i) for i in a]
a.sort()

for i in range(N):
    if a[i] > x:
        print(ans)
        break
    else:
        x -= a[i]
        if i != (N - 1):
            ans += 1
        else:
            if x == 0:
                ans += 1
            print(ans)
s = input()
count = 0
k = 0
for i in s:
    if i == "?":
        k += 1
    else:
        break
for i in range(10**(len(s)-k-1), 10**(len(s))):
    if i % 13 == 5:
        flag = True
        i_str = str(i)
        if len(i_str) < len(s):
            i_str = "0" * (len(s) - len(i_str)) + i_str
        for j in range(len(s)):
            if s[j] == "?" or i_str[j] == s[j]:
                continue
            else:
                flag = False
                break
        if flag == True:
            count += 1
print(count % (10**9 + 7))


### FIXED CODE ###

s = input()
dp = [[0 for i in range(13)]]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1
        
d = [1]   
for i in range(1,len(s)):
    dp.append([0]*13)
    d.append(d[i-1]*10 % 13)
    for r in range(13):
        if s[-(i+1)] == "?":
            for k in range(10): 
                dp[i][(k * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)
                
        else:
            dp[i][(int(s[-(i+1)]) * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)

print(dp[len(s)-1][5]%(10**9+7))
import numpy as np
import itertools
 
H, W, K = list(map(int, input().split())) 
C = []
for i in range(H):
    C.append((input().replace(".","0").replace("#","1")))

C_arr = np.array(C)
 
In = np.array(list(itertools.product([0,1] , repeat=H)))
Out = np.array(list(itertolls.product([0,1] , repeat=W)))
 
ans = 0
for i in range(2**H):
  for j in range(2**W):
    In_matrix = np.diag(In[i])
    Out_matrix = np.diag(Out[j])
    
    In_C = np.dot(In_matrix , C_arr)
    In_C_Out = np.dot(In_C , Out_matrix)
    
    ICO = In_C_Out.flatten()
    ICO = ICO.tolist()
    
    if ICO.count(1) == k:
      ans += 1
      
print(ans)

### FIXED CODE ###

H, W, K = list(map(int, input().split()))
 
c = [list(input()) for i in range(H)]
 
cnt = 0
for i in range(2**H):
    for j in range(2**W):
        cnt_black = 0
        for k in range(H):
            if (i >> k) & 1:
                continue
            for l in range(W):
                if (j >> l) & 1:
                    continue
                if c[k][l] == '#':
                    cnt_black += 1
        if cnt_black == K:
            cnt += 1
 
print(cnt)
A,B,C,D,E,F= map(int, input().split())
res_dict = {}
x_list = []
for i in range(F // A + 1):
    for j in range((F - 100 * A * i) // B + 1):
        x = 100 * (i * A + j * B)
        if x <= F:
            x_list.append(x)
x_uniq = list(set(x_list))
for x in x_uniq:
    for i in range((F - x) // C + 1):
        for j in range((F - x - C * i ) // D + 1):
            y = i * C + j * D
            if x + y <= F and x + y != 0 and x != 0 and ((y / (x + y) <= (E / (100 + E)))):
                res_dict[x] = y
res_dict2 = {}
for i in res_dict:
    res_dict2[res_dict[i]/i] = i
print(res_dict)
print("{0} {1}".format(int(((1 + max(res_dict2))*res_dict2[max(res_dict2)])),int(max(res_dict2)*res_dict2[max(res_dict2)])))

### FIXED CODE ###

N = int(input())
A = int(input())
print(N**2-A)
n,w=map(int,input().split())
weight=[]
value=[]
for i in range(n):
    q,r=map(int,input().split())
    weight.append(q)
    value.append(r)

dp=[[0 for _ in range(10100)] for _ in range(110)]

for i in range(n):
    for j in range(w+1):
        if j-weight[i]>=0:
            dp[i+1][j]=max(dp[i+1][j],dp[i][j-weight[i]]+value[i])
        dp[i+1][j]=max(dp[i+1][j],dp[i][j])

print(dp[n][w])

### FIXED CODE ###

n,w=map(int,input().split())
weight=[]
value=[]
for i in range(n):
    q,r=map(int,input().split())
    weight.append(q)
    value.append(r)

dp=[[0 for i in range(100111)] for j in range(111)]

for i in range(0,n):
    for sum_w in range(0,w+1):
        if sum_w-weight[i]>=0:
            dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w-weight[i]]+value[i])
        dp[i+1][sum_w]=max(dp[i][sum_w],dp[i+1][sum_w])

print(dp[n][w])
def e(x,y):
 A[y][x]='0'
 for t in range(-3,4):
  if 0<=x+dx<8 and A[y][x+dx]=='1':e(x+dx,y)
  if 0<=y+dy<8 and A[y+dy][x]=='1':e(x,y+dy)

for i in range(int(input())):
 print(f'Data {i+1}:')
 input()
 A=[list(input())for _ in[0]*8]
 e(int(input())-1,int(input())-1)
 for r in A:print(*r,sep='')


### FIXED CODE ###

def b(x,y):
 A[y][x]='0'
 for d in range(-3,4):
  0<=x+d<8and'1'==A[y][x+d]and b(x+d,y)
  0<=y+d<8and'1'==A[y+d][x]and b(x,y+d)
e=input
for i in range(int(e())):
 print(f'Data {i+1}:')
 e()
 A=[list(e())for _ in[0]*8]
 b(int(e())-1,int(e())-1)
 for r in A:print(*r,sep='')
a,b,c=map(int,input().split())
d=a<b<c ? "Yes" : "No"
print(d)

### FIXED CODE ###

a,b,c=map(int,input().split())
print(('No','Yes')[a<b<c])
# ==================================================-
# 二分探索
# functionを満たす,search_listの最大の要素を出力
# 【注意点】searchリストの初めの方はfunctionを満たし、後ろに行くにつれて満たさなくなるべき
import math
import sys

sys.setrecursionlimit(10 ** 9)


def binary_research(start, end,function):
    if start == end:
        return start
    middle = math.ceil((start + end) / 2)
    if function(middle, k, a_sum, b_sum):
        start = middle
    else:
        end = middle - 1
    return binary_research(start, end, function)


# ==================================================-

n, m, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
a_sum = [0]
b_sum = [0]
for book in a:
    a_sum.append(a_sum[-1] + book)
for book in b:
    b_sum.append(b_sum[-1] + book)


def can_read(num, k, a_sum, b_sum):
    min_read_time = 1000000000000
    for i in range(min(max(0, num - m),n), n + 1):
        a_num = i
        b_num = num - i
        min_read_time = min(min_read_time, a_sum[a_num] + b_sum[b_num])
    if min_read_time <= k:
        return True
    return False


start = 0
end = n + m

print(binary_research(start, end, can_read))

### FIXED CODE ###

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

def make_sumlist(book_list):
    sumnum=0
    container=[0]
    for i in book_list:
        container.append(sumnum+i)
        sumnum+=i
    return container

total_a=make_sumlist(a)
total_b=make_sumlist(b)

# print(n,m,k)
# print(total_a)
# print(total_b)


#r個読めるか
def readable(r):
    #全部読んでも無理
    if r>n+m:
        return False
    if r==0:
        return True
    max_book=100000000000
    for a_n in range(max(0,r-m),min(n,r)+1):
        b_n=r-a_n
        # print(a_n,b_n)
        book_sum=total_a[a_n]+total_b[b_n]
        # print(book_sum)
        max_book=min(max_book,book_sum)
    if max_book<=k:
        return True
    return False

def nibuntansaku(start,end):
    if start==end:
        return start
    middle=(start+end)//2+1
    if readable(middle):
        start=middle
    else:
        end=middle-1
    return nibuntansaku(start,end)

print(nibuntansaku(0,k))
S = input()
target = "keyence"
length = len(target)

for i in range(length):
  first = target[:i]
  second = target[i:]
  if first == '' and second in S  or first != '' first in S and second in S and S.find(first) <= S.find(second):
    print("YES")
    exit()
print("NO")


### FIXED CODE ###

S = input()
target = "keyence"
length = len(target)+1

# 部分文字列を取り除く方法は、
# 1. 先頭の文字列を削除
# 2. 真ん中の文字列を削除
# 3. 末尾の文字列を削除

if target in S: # 1 & 3
    print("YES")
    exit()
else: # 2
    for i in range(1, length):
      first = target[:i]
      second = target[i:]
      # print("{} + {}".format(S[0:len(first)], S[len(target)-len(second):len(target)]))
      if first in S and second in S and S.find(first) < S.rfind(second):
          if S[0:len(first)] + S[len(S)-len(second):len(S)] == target:
                print("YES")
                exit()
print("NO")
N,W=map(int,input().split())
weight=[]
value=[]
for i in range(N):
    w,v=map(int,input().split())
    weight.append(w)
    value.append(v)
inf=float('inf')
dp=[[-inf for i in range(W+1)] for j in range(N+1)]
for i in range(W+1):
    dp[0][i]=0
for i in range(N):
    for j in range(W+1):
        if j>=weight[i]:
            dp[i+1][j]=max(dp[i][j],dp[i][j-weight[i]]+value[i])
        else:
            dp[i+1][j]=dp[i][j]
print(dp[W])

### FIXED CODE ###

import numpy as np

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

dp = np.zeros(W+1, dtype=np.int64)

for _ in range(N):
  w,v = map(int,input().split())
  np.maximum(dp[:-w]+v,dp[w:], out=dp[w:])

print(dp[-1])
N = int(input())
A = list(map(int, input().split()))
if A in 0:
    ans = 0
else:
    ans = 1
    check = 10 **18
    for i in range(N):
        ans *= A[i]
        print(ans)
        if ans > check:
            ans = -1
            break
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
if 0 in A:
    ans = 0
else:
    ans = 1
    check = 10 **18
    for i in range(N):
        ans *= A[i]
        if ans > check:
            ans = -1
            break
print(ans)
num_1 = int(input())
num_2 = int(input())
num_3 = int(input())

elif num_1 == 5:
	elif nmu_2 == 5 and num_3 == 7 or nmu_2 == 7 and num_3 == 5:
  		print('Yes')
    else 
    	print('NO')
else:
    	elif nmu_2 == 5 and num_3 == 7 or nmu_2 == 7 and num_3 == 5:
  		print('Yes')
    else 
    	print('NO')


### FIXED CODE ###

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

if 5 in abc and 7 in abc and abc.count(7)==1:
  print('YES')
else:
  print('NO')
N = input()
sn = sum([int(i) for i in str(N)])
if N % sn == 0:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

N = input()
sn = sum([int(i) for i in str(N)])
if int(N) % sn == 0:
    print('Yes')
else:
    print('No')
from operator import itemgetter

i, q = [int(x) for x in input().split(' ')]

root = Node(1)
for idx in range(i-1):
    a, b = [int(x) for x in input().split(' ')]
    root.add_child(a, b)

for _ in range(q):
    p, x = [int(x) for x in input().split(' ')]
    root.set_count(p, x)

root.add_count()

counts = sorted(root.get_counts(), key=itemgetter(0))
print(' '.join([str(x[1]) for x in counts]))


class Node:
    def __init__(self, id):
        self.id = id
        self.count = 0
        self.children = []

    def add_child(self, parent_id, child_id):
        if parent_id < self.id:
            return

        if parent_id == self.id:
            # 追加
            self.children.append(Node(child_id))
            return

        for child in self.children:
            child.add_child(parent_id, child_id)
        return

    def set_count(self, target_id, num, is_count=False):
        # if target_id == self.id:
        #     is_count = True

        # if is_count:
        #     self.count += num

        # for child in self.children:
        #     child.add_count(target_id, num, is_count)
        if target_id < self.id:
            return
        if target_id == self.id:
            self.count += num
            return
        for child in self.children:
            child.set_count(target_id, num, is_count)
        return

    def add_count(self, num=0):
        self.count += num
        for child in self.children:
            child.add_count(self.count)
        return

    def get_counts(self):
        res = [(self.id, self.count)]
        # print(self.id, self.count)
        for child in self.children:
            res += child.get_counts()
        return res


### FIXED CODE ###

a = int(input())
s = input()
 
if a < 3200:
  s = 'red'
print(s)
mod = 10**9+7
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]


def init(n):
    for i in range(2, n):
        fac.append(fac[-1] * i % mod)
        inv.append(-inv[mod % i] * (mod // i) % mod)
        finv.append(finv[-1] * inv[-1] % mod)


def com(n, k, mod):
    if n < 0 or k < 0 or n < k:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


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

if not (X+Y) % 3 == 0:
    print(0)
else:
    n = (Y - 2 * X) // -3
    m = X - (2 * n)
    if n < 0 or m < 0:
        print(0)
    else:
        init(n + m)
        print(com(n + m, n, mod))


### FIXED CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )



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

if not (X+Y) % 3 == 0:
    print(0)
else:
    # 2n + m = X
    # n + 2m = Y
    n = (Y - 2*X) // -3
    m = X - (2 * n)
    if n < 0 or m < 0:
        print(0)
    else:
        print(cmb(n+m, n, mod))
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )



x,y=map(int,input().split())
if (x+y)%3!=0:
  print(0)
else:
  a=int((2*x-y)/3)
  b=int((2*y-x)/3)
  if a>=0 and b>=0:
    print(cmb(a+b,b,mod))
  else:
    print(0)

### FIXED CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )



x,y=map(int,input().split())
if (x+y)%3!=0:
  print(0)
else:
  a=int((2*x-y)/3)
  b=int((2*y-x)/3)
  if a>=0 and b>=0:
    print(cmb(a+b,b,mod))
  else:
    print(0)
n = int(input())
a = list(map(int,input().split()))
b = sum(map(int,input().split()))
c = kist(map(int,input().split()))
for i in range(n-1):
  if a[i+1] == a[i] + 1:
    b += a[i+1]
print(b)
  

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=sum(map(int,input().split()))
c=list(map(int,input().split()))
for i in range(n-1):
    if a[i]+1==a[i+1]:
        b+=c[a[i]-1]
print(b)
lst = list(input())
cnt = 0
len_lst = []
for i in lst:
    if i == 'A' or\
       i == 'T' or\
       i == 'C' or\
       i == 'G':
        cnt += 1
    else:
        len_lst.append(cnt)
        cnt = 0
print(max(len_lst))

### FIXED CODE ###

lst = list(input())
cnt = 0
len_lst = []
for i in lst:
    if i == 'A' or\
       i == 'T' or\
       i == 'C' or\
       i == 'G':
        cnt += 1
        len_lst.append(cnt)
    else:
        len_lst.append(cnt)
        cnt = 0
print(max(len_lst))
def gcd(x, y):
    while y!=0:
        x, y = y, x%y
    return x

def process():
    n = int(raw_input().strip())
    for x in xrange(n>>2, 3501):
        for y in xrange(x, 3501):
            b = x*y/gcd(x, y)
            b = b*n/gcd(b, n)
            a = b*4/n
            a -= b/x
            a -= b/y
            r = gcd(a, b)
            a /= r
            b /= r
            if a==1:
                print str(x)+' '+str(y)+' '+str(b)
                return

process()

### FIXED CODE ###

def gcd(x, y):
    while y!=0:
        x, y = y, x%y
    return x

def process():
    n = int(raw_input().strip())
    if n%2 == 0:
        print str(n)+' '+str(n)+' '+str(n>>1)
        return
    for x in xrange(max(n>>1, 1), 3501):
        for y in xrange(x, 3501):
            b = n*x*y
            a = 4*x*y-n*x-n*y
            if a>0 and (b%a)==0:
                print str(x)+' '+str(y)+' '+str(b/a)
                return

process()
n = int(input())
b = [int(i) for i in input().split()]
flag = True
for i in range(n):
    if b[i] > i+1:
        flag = False
        break

if not flag:
    print(-1)
else:
    ans = []
    while len(b) > 0:
        for m in range(max(b), 0, -1):
            if b[m-1] == m:
                ans.append(b[m-1])
                del b[m-1]
                break
ans = ans[::-1]
print(*ans, sep="\n")


### FIXED CODE ###

n = int(input())
b = [int(i) for i in input().split()]
flag = True
for i in range(n):
    if b[i] > i+1:
        flag = False
        break

if not flag:
    print(-1)
else:
    ans = []
    while len(b) > 0:
        for m in range(max(b), 0, -1):
            if b[m-1] == m:
                ans.append(b[m-1])
                del b[m-1]
                break
    ans = ans[::-1]
    print(*ans, sep="\n")