Harryxun/stf_run huggingface dataset:
import sys
import math
MOD = 10 ** 9 + 7

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

def mod_inv(a):
    x = extgcd(a,MOD)[0]
    return (MOD+x%MOD)%MOD

input = sys.stdin.readline
n,a,b = map(int,input().split())
x1 = 1

a = min(a,n-a)
b = min(b,n-b)
if a > b:
    a,b = b,a

for i in range(n-a+1,n+1):
    x1 = x1 * i % MOD
for i in range(1,a+1):
    x1 = x1 * mod_inv(i)

x2 = x1
for i in range(n-b+1,n-a+1):
    x2 = x2 * i % MOD
for i in range(a+1,b+1):
    x2 = x2 * mod_inv(i)
    x2 = x2 % MOD

t = []
nn = n
while nn > 0:
    t.append[nn % 2]
    nn //= 2
t.reverse()
x0 = 1
for i in t:
    x0 = x0 ** 2
    x0 = x0 % MOD
    if i == 1:
        x0 *= 2
        x0 = x0 % MOD
print ((x0 - x1 - x2 - 1) % MOD)




### FIXED CODE ###

import sys
import math
MOD = 10 ** 9 + 7

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

def mod_inv(a):
    x = extgcd(a,MOD)[0]
    return (MOD+x%MOD)%MOD

input = sys.stdin.readline
n,a,b = map(int,input().split())
x1 = 1

a = min(a,n-a)
b = min(b,n-b)
if a > b:
    a,b = b,a

for i in range(n-a+1,n+1):
    x1 = x1 * i % MOD
x11 = 1
for i in range(1,a+1):
    x11 = x11 * i % MOD
x1 = x1 * mod_inv(x11) % MOD

x2 = x1
for i in range(n-b+1,n-a+1):
    x2 = x2 * i % MOD
x21 = 1
for i in range(a+1,b+1):
    x21 = x21 * i % MOD
x2 = x2 * mod_inv(x21) % MOD

t = []
nn = n
while nn > 0:
    t.append(nn % 2)
    nn //= 2
x0 = 1
for i in range(len(t)):
    x0 = x0 ** 2
    x0 = x0 % MOD
    if t[len(t)-i-1] == 1:
        x0 *= 2
        x0 = x0 % MOD
print ((x0 - x1 - x2 - 1) % MOD)
import math

s = map(int,raw_input().split(" "))
print math.sqrt((s[0] - s[2]) ** 2 + (s[1] - s[3]) ** 2)

### FIXED CODE ###

import math

s = map(float,raw_input().split(" "))
print math.sqrt((s[0] - s[2]) ** 2 + (s[1] - s[3]) ** 2)
N = int(input())
s_list = []
count = 0
n, m, l = 0, 0, 0

for i in range(N):
  s = input()
  s_list.append(s)
  count += s.count('AB')
  if s[0] == 'B' and s[-1] == 'A':
    n += 1
    continue
  elif s[-1] == 'A':
    m += 1
  elif s[0] == 'B':
    l += 1

if n < m and n < l:
  print(int(count + 2 * n + min(m - n, l - n)))
else:
  print(int(count + 2 * n))

  

### FIXED CODE ###

N, K = [int(x) for x in input().split(' ')]

output = N - K + 1

print(int(output))
a, b = map(int, input())
if b % a == 0:
  print(a + b)
else:
  print(b - a)

### FIXED CODE ###

a, b = map(int, input().split())
if b % a == 0:
  print(a + b)
else:
  print(b - a)
import sys
lines = sys.stdin.readlines()
line1 = lines.pop(0).split(' ')
#print(line1)
N = int(line1[0])
M = int(line1[1])

#print(N)
#print(M)

str = [0] * N
ans = []
flg = 0
flg2 = 0
for i in range(M):
  line = lines.pop(0).split(' ')
#  print(line)
  s = int(line[0])
  c = int(line[1])
#  print(s)
#  print(c)
  str[s-1] = c
#  print('str = ')
#  print(str)
  one = int(str[0])
  if N == 3:
    ret = one*100 + int(str[1])*10 + int(str[2])
    if int(str[1])>0:
      flg = 1
    if int(str[2])>0:
      flg2 = 1
  elif N == 2:
    ret = one*10 + int(str[1])
    if int(str[1]) > 0:
      flg = 1
  else:
    ret = one
  ans.append(ret)

#print(ans)

for obj in ans[:]:
  if (obj / (10**(N-1))) < 1 and N > 1:
    ans.remove(obj)
    
  if N == 2:
    if flg == 1:
      a = obj % 10
      if a == 0:
#        print('リムーブ')
        ans.remove(obj)

  elif N == 3:
    if flg == 1 and flg2 ==1:
#      print('リムーブ候補')
#      print(obj)
      if obj % 100 == 0:
#        print('リムーブ')
        ans.remove(obj)
      elif obj % 10 == 0:
#        print('リムーブ')
        ans.remove(obj)
    elif flg == 0 and flg2 ==1:
#      print('リムーブ候補')
#      print(obj)
      b = obj % 10
      print(b)
      if b == 0:
#        print('リムーブ')
        ans.remove(obj)

if not ans:
  print('-1')
else:
#  print(ans)
  print(min(ans))


### FIXED CODE ###

import math
print(math.ceil(int(input()) / 2))
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,M,V,P=map(int,input().split())
A=sorted(list(map(int,input().split())))
_SUM=sum(A[:N-(P-1)])



def main(s):
    tempSUM=_SUM-s
    s+=M
    a=(V-P)

    if s<A[-P]:
        return(0)
    else:
        if a>0:
            tempSUM+=a*M
            if s>tempSUM//(N-P)) or s==tempSUM//(N-P)) and tempSUM%(N-P)) == 0:
                return(1)
        else:
            return(1)


if main(A[0]):
    print(N)
    exit()
st=0
end=N-1

while 1:
    a=(st+end)//2
    if main(A[a]):
        end=a
    else:
        st=a

    if end-st<=1:
        break

if main(A[st]):
    print(N-st)
else:
    print(N-end)


### FIXED CODE ###

# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,M,V,P=map(int,input().split())
A=sorted(list(map(int,input().split())))
_SUM=sum(A[:N-(P-1)])



def main(i):

    B=[A[m] for m in range(N-(P-1)) if m!=i]

    C=A[i]+M
    a=V-P

    if C<A[-P]:
        return(0)
    else:
        if a>0:
            Votenum=a*M
            for b in B:
                Votenum-=min(C-b,M)
                if Votenum<=0:
                    return(1)

            return(0)
        else:
            return(1)




if main(0):
    print(N)
    exit()
st=0
end=N-P+1

while 1:
    a=(st+end)//2
    if main(a):
        end=a
    else:
        st=a

    if end-st<=1:
        break

if main(st):
    print(N-st)
else:
    print(N-end)
def main():
	N, K = map(int,input().split())
	A = list(map(int,input().split()))
	A.sort()
	l, r = 0, N-1
	while l < r:
		m = (l+r)>>1
		p = True
		if m == 0 and solve(N, K, A[1:], A[0]):
			l = m+1
			continue
		if solve(N, K, A[:m]+A[m+1:], A[m]):
			l = m+1
		else:
			r = m
	if l == N-1 and solve(N, K, A[:N-1], A[N-1]):
		l = N
	print(l)


def solve(n, k, a, ai):
	dp = [[False for _ in range(k+1)] for _ in range(n)]
	dp[0][0] = True
	if a[0] > k:
		dp[0][k] = True
	else:
		dp[0][a[0]] = True
	for i in range(1, n-1):
		for j in range(k-1):
			if not dp[i-1][j]:
				continue
			dp[i][j] = True
			if j + a[i] > k:
				dp[i][k] = True
			else:
				dp[i][j+a[i]] = True
	return not any(map(lambda j: dp[n-2][j], range(k-ai, k)))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
	N, K = map(int,input().split())
	A = list(map(int,input().split()))
	A.sort(reverse=True)
	no_need = 0
	sub = 0
	for ai in A:
		if sub+ai < K:
			sub += ai
			no_need += 1
		else:
			no_need = 0

	print(no_need)


if __name__ == '__main__':
    main()
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M: int, X: int, Y: int, x: "List[int]", y: "List[int]"):
    xs = {X, *x}
    ys = {Y, *y}
    x1 = min(xs)
    x2 = max(xs)
    y1 = min(ys)
    y2 = max(ys)
    print("No War" if (x2 < y1 or y2 < x1) else "War")


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    x = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    y = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, X, Y, x, y)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M: int, X: int, Y: int, x: "List[int]", y: "List[int]"):
    xs = set(x)
    xs.add(X)
    ys = set(y)
    ys.add(Y)
    x1 = min(xs)
    x2 = max(xs)
    y1 = min(ys)
    y2 = max(ys)
    print("No War" if (x2 < y1 or y2 < x1) else "War")


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    x = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    y = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, X, Y, x, y)


if __name__ == '__main__':
    main()
i = input()
idx = 0

while idx < i:
  	cnt = 0
	for _ in range(3):
      d1, d2 = list(map(int, input.split(' ')))
      if d1 == d2:
        cnt += 1
    if cnt == 3:
      print('Yes')
    else:
      idx += 1

print('No')

### FIXED CODE ###

N = int(input())
lst = []
for _ in range(N):
  d1, d2 = map(int, input().split(' '))
  lst.append((d1, d2))
  
idx = 0
flag = False
while idx < N-2:
  cnt = 0
  for i in range(3):
    d1, d2 = lst[i+idx]
    if d1 == d2:
      cnt += 1
  if cnt == 3:
    flag = True
    break
  else:
    idx += 1
 
print('Yes' if flag else 'No')
import itertools,sys
def f(a):
 if len(a)<2:yield[a[0]]*2
 for i in range(1,len(a)):
  for p,s in f(a[:i]):
   for q,t in f(a[i:]):
    yield(p+q,f'({s} + {t})')
    yield(p-q,f'({s} - {t})')
    yield(p*q,f'({s} * {t})')
def s(a):
 for p in itertools.permutations(a):
  for n,s in f(p):
   if n==10:print(s);return 1
for e in iter(input,'0 0 0 0\n'):
 a=list(map(int,e.split()))
 if not s(a):print(0)


### FIXED CODE ###

from itertools import *
g=lambda a,x,b:{'+':a+b,'-':a-b,'*':a*b}[x]
def f(s):
 for a,b,c,d in permutations(s):
  for x,y,z in product('+-*',repeat=3):
   if g(g(g(a,x,b),y,c),z,d)==10:return f"(({a}{x}{b}){y}{c}){z}{d}"
   if g(g(a,x,b),y,g(c,z,d))==10:return f"({a}{x}{b}){y}({c}{z}{d})"
 return 0
for e in iter(input,'0 0 0 0'):print(f(list(map(int,e.split()))))
n = int(input())
x = list(map(int,input().split()))
y = sorted(x)
l = y[n/2-2]
r = y[n/2-1]
for i in range(n):
    if x[I] <= l:print(r)
    else:print(l)


### FIXED CODE ###

n = int(input())
x = list(map(int,input().split()))
y = sorted(x)
l = y[n//2-1]
r = y[n//2]
for i in range(n):
    if x[i] <= l:print(r)
    else:print(l)
n, x, t = map(int, input().split())
if n%x==0:
  print(n*t/x)
else:
  print(((int(n/x)+1)*t)

### FIXED CODE ###

n, x, t = map(int, input().split())
if n%x==0:
  print((n//x)*t)
else:
  print( ((n//x)+1)*t )
def search(x, y, m):
    if x >= len(m[0]) or y >= len(m):
        return 0
    if m[y][x] == '#':
        return 0
    m[y][x] = '#'
    return 1 + search(x+1,y, m) + search(x-1,y,m) \
            + search(x,y+1,m) + search(x,y-1,m)

while True:
    w, h = map(int, input().split())
    if w == 0: break
    room = []
    for i in range(h):
        tmp = list(input())
        room.append(tmp[:w])
        if '@' in tmp:
            y = i
            x = tmp.index('@') 
    print(search(x, y, room))

### FIXED CODE ###

def search(x, y, m):
    if x < 0 or y < 0 \
            or x >= len(m[0]) or y >= len(m):
        return 0
    if m[y][x] == '#':
        return 0
    m[y][x] = '#'
    return 1 + search(x+1,y, m) + search(x-1,y,m) \
            + search(x,y+1,m) + search(x,y-1,m)

while True:
    w, h = map(int, input().split())
    if w == 0: break
    room = []
    for i in range(h):
        tmp = list(input())
        room.append(tmp[:w])
        if '@' in tmp:
            y = i
            x = tmp.index('@') 
    print(search(x, y, room))
S = str(input())
n = int(input())
Q = [list(map(str, input().split())) for _ in range(n)]
cnt = 0
# for q in Q:
#     if q[0] == "1":
#         cnt += 1
# #         S.reverse()
#     elif q[0] == "2":
#         if (int(q[1])+cnt)%2 == 1:
#             S.insert(0,q[2])
#         else:
#             S.append(q[2])
for q in Q:
    if q[0] == "1":
        cnt += 1
    elif q[0] == "2":
        if (int(q[1])+cnt)%2 == 1:
            S = q[2] + S
        else:
            S = S + q[2]

if cnt%2==1:
    S.reverse()
print("".join(S))

### FIXED CODE ###

S = str(input())
n = int(input())
Q = [list(map(str, input().split())) for _ in range(n)]
cnt = 0
s_pre = ""
s_pro = ""
for q in Q:
    if q[0] == "1":
        cnt += 1
    else:
        if (int(q[1])+cnt)%2 == 1:
#             S = q[2] + S
            s_pre = q[2] + s_pre
        else:
            s_pro = s_pro + q[2]
#             S = S + q[2]

S = s_pre + S + s_pro
if cnt%2==1:
    S = list(S)
    S.reverse()
print("".join(S))
def test(n):
  m = 0
  if n == 3:
    m += 100000
  elif n == 2:
    m += 200000
  elif n == 1:
    m += 300000
  return m

x, y = int(input())
ans = test(x) + test(y)
if ans == 600000:
  ans += 400000

print(ans)

### FIXED CODE ###

def test(n):
  m = 0
  if n == 3:
    m += 100000
  elif n == 2:
    m += 200000
  elif n == 1:
    m += 300000
  return m

x, y = map(int, input().split())
ans = test(x) + test(y)
if ans == 600000:
  ans += 400000

print(ans)
a = int(input("a"))
b = int(input("b"))
c = (a+b)/2
if c % 1 == 0:
    print(c)
else:
    print("IMPOSSIBLE")


### FIXED CODE ###

a,b = (int(x) for x in input().split())
c = (a+b)/2
if c % 1 == 0:
    print(round(c))
else:
    print("IMPOSSIBLE")
i = int(input())
num = map(int, input().split())
count = 0
while True:
  for k in range(i):
    num[k] =/ 2
    if type(num[k]) is float or num[k] == 0:
      break
    count += 1
print(count)


### FIXED CODE ###

i = int(input())
num = list(map(int, input().split()))
count = 0
while True:
  flag = False
  for k in range(i):
    if num[k] % 2 != 0:
      flag = True
  if flag:
    break
  for k in range(i):
    num[k] /= 2
  count += 1
print(count)
N, M = map(int, input().split())
data = [[] for i in range(M)]
ans = [""] * M
num = [0] * (M+1)
for i in range(M):
    ken, year = map(int, input().split())
    data[i] = [ken, year, i]
    
data.sort(key=lambda x:x[1])

for p, y, i in data:
    num[p] += 1
    ans[i] = (str(p).zfill(6) + str(num[p]).zfill(6))

for i in ans:
    print(i)

### FIXED CODE ###

N, M = map(int, input().split())
cnt = [0 for i in range(N + 1)] 
check = []
ans = []

for i in range(M):
    p, y = map(int, input().split())
    check.append((y, p, i))

check.sort()

for y, p, i in check:
    cnt[p] += 1
    ans.append((i,str(p).zfill(6)+str(cnt[p]).zfill(6)))

ans.sort()

for aa, bb in ans:
    print(bb)
n=int(input())
s,p=list(map(int,input().split()))
li=[]
for i in range(0,n):
  li.append((i+1,s[i],p[i]))

new_li=sorted(li,key=lambda x:x[1])
new2_li=sorted(new_li,key=lambda x:x[2])

for j in range(0,n):
  print(new2_li[j][0])

### FIXED CODE ###

a,p=map(int,input().split())
x=3*a+p
print(x//2)
import math
while 1:
    e = int(input())
    if  e == 0 :break
    m = e
    for z in range(e):
        for y in range(int(math.sqrt(e))+ 1):
            if  e-y**2-z**3+y+z < 0 or e - y**2 -z**3 <0:break
            if m > e-y**2-z**3+y+z: m =  e-y**2-z**3+y+z
    print(m)



### FIXED CODE ###

import math
while 1:
    e = int(input().strip())
    if e ==0:break
    m=e
    z =0
    while z**3 <= e:
        y = int(math.sqrt(e-z**3))
        x = e - y**2- z**3 
        if x < 0:break
        if m > x+y+z: m = x+y+z    
        z+=1
    print(m)
s = input()
n = len(s)

sa = s[:(n - 1) // 2]
sb = s[(n + 1) // 2:]

if s == s[::-1] and a == a[::-1] and b == b[::-1]:
  print("Yes")
  
else:
  print("No")


### FIXED CODE ###

s = input()
n = len(s)

sa = s[:(n - 1) // 2]
sb = s[(n + 1) // 2:]

if s == s[::-1] and sa == sa[::-1] and sb == sb[::-1]:
  print("Yes")
  
else:
  print("No")
#16D8101023J 久保田凌弥 kubotarouxxx python3

x,y=map(int, raw_input().split())
w=x*y
z=2*x+2*y

print(w,z)



### FIXED CODE ###

#16D8101023J 久保田凌弥 kubotarouxxx python3

x,y=map(int, input().split())
w=x*y
z=2*x+2*y

print(w,z)

#
import sys

sys.setrecursionlimit(10**9)

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


checked= {}
graph = {}
for i in range(m):
    a,b,c = map(int, input().split())

    if a in graph:
        graph[a].append((b,c))
    else:
        graph[a] = []
        graph[a].append((b,c))

ans = -1*float("inf")
def solve(node, current_score):
    global ans
    if node == n:
        if n in graph:
            for tmp in graph[n]:
                if tmp[0] == 1:
                    flag = True
            if not flag:
                if ans < current_score:
                    ans = current_score 
            else:
                print("inf")
                exit()
        else:
            if ans < current_score:
                ans = current_score 

    if node in graph:
        for g in graph[node]:
            solve(g[0], current_score + g[1])


solve(1,0)
print(ans)

### FIXED CODE ###

INF = float("inf")
n, m = map(int, input().split())
edges = [None] * m

# n:node num
# e:edges
# s:start node

d = [INF] * n
d[0] = 0
def Bellmanford(n, e, s):

    # 経路は最大でもN-1回移動すると終わるので（閉路がない限り）その分だけ更新
    for i in range(n):
        # すべての辺についてみていく
        for a,b,c in e:
            # aにたどり着ける（コストがINFではない）かつ、今のところのbまでのコストがa->bで行くときより大きい場合、更新
            if d[a] != INF and d[a] + c < d[b]:
                d[b] = d[a] + c

                # N回目更新した際に、それでも最終地点Nまでのコストが更新されたー＞負の閉路がある
                if i == n-1 and b == n-1:
                    return INF


    return -1 * d[-1]



for i in range(m):
    A, B, C = map(int, input().split())
    edges[i] = (A-1, B-1, -C)

ans = Bellmanford(n, edges, 0)
print(ans)
n = int(input()) 
a = [int(input()) for i in range(n)] 

used = [a[0]]
pre = a[0]
for i in a[1:]:
    if i not in used and pre[-1] == i[0]:
        used.append(i)
        pre = i
    else:
        print("No")
        exit()

print("Yes")

### FIXED CODE ###

n = int(input()) 
a = [input() for i in range(n)] 

used = [a[0]]
pre = a[0]
for i in a[1:]:
    if i not in used and pre[-1] == i[0]:
        used.append(i)
        pre = i
    else:
        print("No")
        exit()

print("Yes")
i = input().split()
s, t = map(int, i)
str_list = []

for i in range(s):
    string = input()
    str_list.append(string)

str_list.sort()
ans = ''.join(str_list)

print(ans)

### FIXED CODE ###

a,b,c = input().split()
 
a = int(a)
b = int(b)
c = int(c)
 
 
if(a + b + c) != 17:
  print("NO")
elif(a + b + c) == 17:
    if(a + b == 10) | (b + c == 10) | (c + a == 10):
      print("YES")
    else:
      print("NO")
else:
  print("NO")
from heapq import heappop, heappush, heapify
n, m = map(int, input().split())
a = [-int(i) for i in input().split()]

heapify(a)
for _ in range(m):
  l = heappop(a)
  heappush(a, -((-l)//2))
  print(l,a)

print(-sum(a))

### FIXED CODE ###

from heapq import heappop, heappush, heapify
n, m = map(int, input().split())
a = [-int(i) for i in input().split()]

heapify(a)
for _ in range(m):
  l = heappop(a)
  heappush(a, -((-l)//2))

print(-sum(a))
A,B = map(int, input().split())
if (A==1) and (B==2):
    print(3)
if (A==2) and (B==3):
    print(1)
if (A==3) and (B==1):
    print(2)

### FIXED CODE ###

A = int(input())
B = int(input())
if A+B == 3:
    print(3)
elif A+B == 4:
    print(2)
else:
    print(1)
N = map(int, input())
L_list = list(map(int, input().split()))
sum = 0

L_list.sort()

from bisect import bisect_left
# print(bisect_left(L_list, 3))

for i in range(N):
    for j in range(i+1, N):
        t = L_list[i]+L_list[j]
        idx = bisect_left(L_list, t)
        sum += max(0, idx-(j+1))
        
print(sum)

### FIXED CODE ###

N = int(input())
L_list = list(map(int, input().split()))
sum = 0

L_list.sort()

from bisect import bisect_left

for i in range(N):
    for j in range(i+1, N):
        t = L_list[i]+L_list[j]
        idx = bisect_left(L_list, t)
        sum += max(0, idx-(j+1))
        
print(sum)
N = int(input())
arr = map(int, input().split(' '))
ans = [0 for x in range(N)]
for i in reversed(range(N)):
  n = i + 1
  if i > N/2.0:
    ans[i] == 0:
  else:
    s = 0
  	for k in reversed(range(1, N // n)):
    	index = n*k - 1
        s += arr[index]
    if s % 2 == arr[i]:
      arr[i] = 0
    else:
      arr[i] = 1
    	
ans_arr = []
for i in ans:
  if ans == 1:
    ans_arr.append(i)

print(sum(ans))
print(' '.join(ans_arr))


### FIXED CODE ###

def main():
    n = int(input())
    A = [0] + list(map(int, input().rstrip().split()))
    for i in range(n // 2, 0, -1):  # second half: no multiples
        A[i] = sum(A[i::i]) % 2
    ans = [i for i, j in enumerate(A) if j]
    print(len(ans))  # all cells: [1] -> len() (much faster than sum())
    print(*ans)


if __name__ == "__main__":
    main()
L = int(input())
# ノード数を決める
for i in range(1,21):
    if (1 << i) > L:
        node = i
        break

# 必ず 0と2^Nの辺を貼る
edge = []
for i in range(node-1):
    edge.append((i+1,i+2,0))
    edge.append((i+1,i+2,1<<i))

# 2の累乗の区間に分割
for i in range(node-1):
    if (L >> i) & 1:
        edge.append((i+1,node,L-(1<<i)))
        L = L-(1<<i)

#出力
print(str(dig) + " " + str(len(edge)))
s = "{0} {1} {2}"
for v,v2,w in edge:
    print(s.format(v,v2,w))

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 終了後に解説を見て解けた
# パス数が２のべき乗であれば簡単にグラフを構築できることに気付きたかった。
#
# 本番中は、10進法で考えて 頂点1と頂点2の間を辺{0, 100, 200, ..., 900}で繋ぎ、頂点2と頂点3の間を辺{0, 10, ..., 90}で繋ぎ、
# などという事を考えていたが、それ以上進展させることが難しかった。


import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import random
import re
import string
import sys

L = int(input())

v = 1
edges = []  # (from, to, cost)

# L = 37の場合を例にとりコメントを付与
# まず長さ0 ~ 31までのパスを作成する。
#   頂点1 -> 頂点2を0の辺と1の辺で結ぶ
#   頂点2 -> 頂点3を0の辺と2の辺で結ぶ
#   頂点3 -> 頂点4を0の辺と4の辺で結ぶ
#   頂点4 -> 頂点5を0の辺と8の辺で結ぶ
#   頂点5 -> 頂点6を0の辺と16の辺で結ぶ
n = 2
cost = 1
while n <= L:
    edges.append((v, v+1, 0))
    edges.append((v, v+1, cost))
    cost *= 2
    v += 1
    n *= 2

# 頂点6をv_sink(最終到達点)とする
v_sink = v

# ここから先、長さ32, 33, 34, 35, 36のパスを生成することになる。
# 頂点3と頂点6を、32の辺で直でつなぐと、長さ32, 33, 34, 35のパスが作れる。
# 頂点1と頂点6を、36の辺で直でつなぐと、長さ36のパスが作れる。
n //= 2
N = n
L -= N

while L > 0:
    if L >= n:
        edges.append((v, v_sink, N))
        L -= n
        N += n
    n //= 2
    v -= 1

print(v_sink, len(edges))
for e in edges:
    print(*e)
n=int(input())
ans=1
for i in range(1,n+1):
  ans=ans*i
print(ans/(10**9+7))

### FIXED CODE ###

n=int(input())
j=1
for i in range(1,n+1):
  j=(j*i)%(10**9+7)
print(j)
#Union Find
import sys
input = sys.stdin.readline
 
n,m = map(int,input().split())

#根なら-size,子なら親の頂点
par = [-1]*n

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x != y:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

def size(x):
    return -par[find(x)]


edge = [tuple(map(int,input().split())) for i in range(m)]
edge = edge[::-1]
for i in range(m):
    edge[i] = (edge[i][0]-1,edge[i][1]-1)

res = []
for i in range(m):
    fi = find(edge[i][0])
    se = find(edge[i][1])
    if fi == se:
        res.append(0)
    else:
        res.append(size(fi)*size)
        unite(fi,se)
ass = 0
for i in range(m):
    ass += res[m-1-i]
    print(ass)

### FIXED CODE ###

import sys
input = sys.stdin.readline

#木の根を求める
def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])

#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x != y:
        #xとyの属している集合が異なる時
        if rank[x] < rank[y]:
            par[x] = y
            size[y] += size[x]
        else:
            par[y] = x
            size[x] += size[y]
            if rank[x]==rank[y]:
                rank[x] += 1

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

########################################
#初期化
n,m = map(int,input().split())

par = [0]*n #親
for i in range(n):
    par[i] = i
rank = [1]*n #深さ
size = [1]*n #size[i]:iを根とするグループのサイズ
edge2 = [[0] for i in range(m)]
for i in range(m):
    edge2[i] = list(map(int,input().split()))

edge = [[0] for i in range(m)]
for i in range(m):
    edge[i] = [edge2[m-1-i][0]-1,edge2[m-1-i][1]-1]
res = []
for i in range(m):
    fi = find(edge[i][0])
    se = find(edge[i][1])
    if fi == se:
        res.append(0)
    else:
        res.append(size[fi]*size[se])
        unite(fi,se)
ass = 0
for i in range(m):
    ass += res[m-1-i]
    print(ass)