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

import sys,math
n = int(input())
a = list(map(int,input().split()))
select = [0 for _ in range(n+1)]
mark = [0 for _ in range(n+1)]
c = 0
for i in range(n-1,0,-1):
    if a[i] ==0 and mark[i+1]%2==1:
        c += 1
        select[i + 1] = 1
        l = 1
        r = (i + 1)
        m = math.sqrt(i+1)
        m = int(m)
        while (l <=m):
            if (i + 1) % l == 0:
                mark[l] += 1
                r = (i + 1) // l
                if l != r:
                    mark[r] += 1
            l += 1
    if a[i] and mark[i+1]%2==0:
        c+=1
        select[i + 1] = 1
        l = 1
        r = (i + 1)
        m = math.sqrt(i + 1)
        m = int(m)
        while (l <= m):
            if (i + 1) % l == 0:
                mark[l] += 1
                r = (i + 1) // l
                if l!=r:
                    mark[r] += 1
            l += 1
if a[0]==0 and mark[1]%2==1:
    c+=1
    select[1]=1
    mark[1]+=1
elif a[0]==1 and mark[1]%2==0:
    c += 1
    select[1] = 1
    mark[1] += 1
print(c)
for i in range(1,n+1):
    if select[i]:
        sys.stdout.write('{} '.format(i))

### FIXED CODE ###

import sys,math
n = int(input())
a = list(map(int,input().split()))
select = [0 for _ in range(n+1)]
mark = [0 for _ in range(n+1)]
c = 0
for i in range(n-1,0,-1):
    if a[i] ==0 and mark[i+1]%2==1:
        c += 1
        select[i + 1] = 1
        l = 1
        r = (i + 1)
        m = math.sqrt(i+1)
        m = int(m)
        while (l <=m):
            if (i + 1) % l == 0:
                mark[l] += 1
                r = (i + 1) // l
                if l != r:
                    mark[r] += 1
            l += 1
    if a[i] and mark[i+1]%2==0:
        c+=1
        select[i + 1] = 1
        l = 1
        r = (i + 1)
        m = math.sqrt(i + 1)
        m = int(m)
        while (l <= m):
            if (i + 1) % l == 0:
                mark[l] += 1
                r = (i + 1) // l
                if l!=r:
                    mark[r] += 1
            l += 1
if a[0]==0 and mark[1]%2==1:
    c+=1
    select[1]=1
    mark[1]+=1
elif a[0]==1 and mark[1]%2==0:
    c += 1
    select[1] = 1
    mark[1] += 1
print(c)
for i in range(1,n+1):
    if select[i]:
        sys.stdout.write('{} '.format(i))
### BUGGY CODE ###

from queue import Queue 
H,W = map(int, input().split())

A = []
queue = Queue()
inf = float('inf')
for i in range(H):
    A.append([0 if c == '#' else inf for c in input()])
    for j in range(W):
        if A[i][j] == 0:
            queue.put([i,j])

mx = 0
dx = [[0,1], [1,0], [-1,0], [0,-1]]
n = queue.qsize()
for _ in range(n):
    i,j = queue.get()
    for x,y in dx:
        if j+x>=W or j+x<0 or i+y>=H or i+y<0:
            continue
        A[i+y][j+x] = A[i][j]+1
        queue.put([i+y, j+x])
        mx = max(A[i][j]+1, mx)

while not queue.empty():
    i,j = queue.get()
    for x,y in dx:
        if j+x>=W or j+x<0 or i+y>=H or i+y<0:
            continue
        if A[i+y][j+x] > A[i][j]+1:
            A[i+y][j+x] = A[i][j]+1
            queue.put([i+y, j+x])
            mx = max(A[i][j]+1, mx)

print(mx)

### FIXED CODE ###

from collections import deque

def bfs(grid, queue, wall):
    ans = 0
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while queue:
        cnt,y,x = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall:
                continue
            queue.append([cnt+1,y_,x_])
            grid[y_][x_] = wall
            ans = max(ans, cnt+1)
    return ans

H,W = map(int, input().split())
wall = '#'
queue = deque([])
edges = [wall for i in range(W+2)]
grid = [edges]

for i in range(1,H+1):
    S = [wall]+list(input().strip())+[wall]
    for j in range(1,W+1):
        if S[j] == wall:
            queue.append([0,i,j])
    grid.append(S)
grid.append(edges)
print(bfs(grid, queue, wall))
### BUGGY CODE ###

n, total = [int(x) for x in input().split()]

def calc_total(yukichi, ichiyo, hideyo):
  return 10000 * yukichi + 5000 * ichiyo + 1000 * hideyo

result_string = ""
for yukichi in range(n + 1):
  for ichiyo in range(n + 1):
    hideyo = max(0, n - yukichi - ichiyo)
    if (calc_total(yukichi, ichiyo, hideyo) == total) and (yukichi + ichiyo + hideyo == n):
      result_string = "{} {} {}".format(yukichi, ichiyo, hideyo)
      break
        
if len(result_string) == 0:
  print("-1 -1 -1")
else:
  print(result_string)

### FIXED CODE ###

n, total = [int(x) for x in input().split()]

def calc_total(yukichi, ichiyo, hideyo):
  return 10000 * yukichi + 5000 * ichiyo + 1000 * hideyo

result_string = ""
for yukichi in range(n + 1):
  for ichiyo in range(n + 1):
    hideyo = n - yukichi - ichiyo
    if hideyo < 0:
      continue
      
    if (calc_total(yukichi, ichiyo, hideyo) == total) and (yukichi + ichiyo + hideyo == n):
      result_string = "{} {} {}".format(yukichi, ichiyo, hideyo)
      break
        
if len(result_string) == 0:
  print("-1 -1 -1")
else:
  print(result_string)
### BUGGY CODE ###

LIM=200002
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
def pop_num2(N,b,L,M):
    if N==0:
        return 0
    if N<=100000:
        return M[N]
    v=N%b
    return pop_num2(v,L[v],L,M)+1

M=[0]*100001
for i in range(1,100001):
    M[i]+=pop_num(i,L[i],L)

X=int(input())
Y=input()
d=bin_sum2(Y)+1
c=bin_sum2(Y)-1
for i in range(X):
    Y_i=Y[:i]+str(abs(int(Y[i])-1))+Y[i+1:]
    if Y_i[i]=="1":
        b=d
    else:
        b=c
    print(pop_num2(int(Y_i,2),b,L,M))

### FIXED CODE ###

from collections import deque
LIM=200004
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200005
for i in range(1,200004):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)
e=int(Y,2)%(d+1)
f=int(Y,2)%max(1,(d-1))
O=[1]*(X+2)
P=[1]*(X+2)
q=max(d-1,1)
for i in range(1,X+1):
    O[i]=O[i-1]*2%q
    P[i]=P[i-1]*2%(d+1)
for i in range(X):
    
    if int(Y[i])==1:
        b=max(d-1,1)
        flag=max(0,d-1)
        g=(f-O[X-1-i]+b)%b
    else:
        b=d+1
        flag=1
        g=(e+P[X-1-i])%b

    if flag==0:
        print(0)
    elif g==0:
        print(1)
    else:
        print(M[g]+1)
### BUGGY CODE ###

from itertools import product
N = int(input())
S = input()
S = [int(s) for s in S]
ans = 0
for q in product(range(10),repeat=3):
    i = 0
    for s in S:
        if s==q[i]:
            if i==2:
                ans += 1
                break
            else:
                i+=1
print (ans)

### FIXED CODE ###

from itertools import product
N = int(input())
S = input()
S = [int(s) for s in S]
ans = 0
for q in product(range(10),repeat=3):
    i = 0
    for s in S:
        if s==q[i]:
            if i==2:
                ans += 1
                break
            else:
                i+=1
print (ans)
### BUGGY CODE ###

S = input()

cnt = 0
idx = 0
while "BW" in S:
    if S[idx:idx+2] == "BW":
        cnt += 1
        S = S[:idx] + "WB" + S[idx+2:]
        idx = 0
    else:
      idx += 1
      
print(cnt)


### FIXED CODE ###

S = input()

ans = 0
cnt = 0
for i in range(len(S)):
    if S[i] == "B":
        cnt += 1
    else:
        ans += cnt
print(ans)
### BUGGY CODE ###

from queue import Queue

H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]

patterns = [[0 for _ in range(W)] for __ in range(H)]
searched = [[False for _ in range(W)] for __ in range(H)]
q = Queue()

div = 10**9+7

def search(x, y):
    if not (0 <= x < W and 0 <= y < H):
        return
    if searched[y][x]:
        return
    searched[y][x] = True
    if field[y][x] == '#':
        return
    res = 0
    if x > 0:
        res += patterns[y][x-1] % div
    if y > 0:
        res += patterns[y-1][x] % div
    patterns[y][x] = res % div
    q.put([x, y])
    return

patterns[0][0] = 1
q.put([0, 0])

while not searched[-1][-1]:
    x, y = q.get()
    search(x+1, y)
    search(x, y+1)
    
print(patterns[-1][-1] % div)


### FIXED CODE ###

H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]

div = 10**9+7

patterns = [[0 for _ in range(W)] for __ in range(H)]
patterns[0][0] = 1


for y in range(H):
    for x in range(W):
        if x + 1 < W and field[y][x+1] != '#':
            patterns[y][x+1] += patterns[y][x] % div
        if y + 1 < H and field[y+1][x] != '#':
            patterns[y+1][x] += patterns[y][x] % div

print(patterns[-1][-1] % div)
### BUGGY CODE ###

def operation(i, ans_list) -> list:
    ans_list.append(i)
    ans_list.reverse()

    return ans_list

n = int(input())
input_list = list(map(str, input().split()))
ans_list = []

for i in input_list:
    operation(i, ans_list)

print(' '.join(ans_list))

### FIXED CODE ###

n = int(input())
input_list = list(map(int, input().split()))
ans_list = input_list[::-2] + input_list[n%2::2]
print(*ans_list)
### BUGGY CODE ###

class grid:
    def __init__(self, word):
        self.word = word
        self.has_golem = 1
        self.will_move_golem = 0

# def show_grid(grids):
#     print("----------------")
#     for g in grids:
#         print("| " + g.word + " ", end="")
#     print("|")

#     for g in grids:
#         print("| " + str(g.has_golem) + " ", end="")
#     print("|")
#     print("----------------")

def move_golem(text, dir, grids):
    for i in range(n):
        if grids[i].word == text and grids[i].has_golem != 0:
            move_golem = grids[i].has_golem
            grids[i].has_golem = 0
            if(dir == 'L' and i != 0):
                grids[i-1].will_move_golem += move_golem
            if(dir == 'R' and i != n-1):
                grids[i+1].will_move_golem += move_golem
        else:
            continue
    for g in grids:
        g.has_golem += g.will_move_golem
        g.will_move_golem = 0

def answer(grids):
    sum_golem = 0
    for g in grids:
        sum_golem += g.has_golem

    return sum_golem

n, q = map(int, input().split())
s = input()

grids = []
for i in range(n):
    grids.append(grid(s[i]))

# show_grid(grids)

for i in range(q):
    text, dir = input().split()
    # print(text + " " + dir)
    move_golem(text, dir, grids)
    # show_grid(grids)

print(answer(grids))


### FIXED CODE ###

class spell:
    def __init__(self, text, dir):
        self.text = text
        self.dir = dir

def isRange(a):
    if(0 <= a < n):
        return True
    else:
        return False

n, q = map(int, input().split())
s = input()

spells = []
for i in range(q):
    text, dir = input().split()
    spells.append(spell(text, dir))


l = -1
r = n

for sp in reversed(spells):
    if(isRange(l+1) and s[l+1] == sp.text and sp.dir == 'L'):
        l += 1
    elif(isRange(l) and s[l] == sp.text and sp.dir == 'R'):
        l -= 1
    if(isRange(r-1) and s[r-1] == sp.text and sp.dir == 'R'):
        r -= 1
    elif(isRange(r) and s[r] == sp.text and sp.dir == 'L'):
        r += 1

print(n-(l+1)-(n-r))
### BUGGY CODE ###

from collections import defaultdict
n = int(input())
li = []
for _ in range(n):
  s = input()
  temp = []
  dd = defaultdict(lambda:0)
  for i in s:
    dd[i] += 1
  for key in dd:
    temp.append((key, dd[key]))
  temp.sort()
  li.append(temp)
li.sort()
ans = 0
k = 0
for i in range(n):
  if i == n-1:
    ans += (k*(k+1))//2
  else:
    if li[i] == li[i+1]:
      k += 1
    else:
      ans += (k*(k+1))//2
      k = 0
print(ans)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
li = []
for _ in range(n):
  s = input()
  temp = []
  dd = defaultdict(lambda:0)
  for i in s:
    dd[i] += 1
  for key in dd:
    temp.append((key, dd[key]))
  temp.sort()
  li.append(temp)
li.sort()
ans = 0
k = 0
for i in range(n):
  if i == n-1:
    ans += (k*(k+1))//2
  else:
    if li[i] == li[i+1]:
      k += 1
    else:
      ans += (k*(k+1))//2
      k = 0
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))

import collections

c = collections.Counter(A)

ans = []
for a in A:
  ans_a = 0
  for k, v in c.items():
    if k == a:
      ans_a += max(v - 1, 0) * max(v - 2, 0) // 2
    else:
      ans_a += v * max(v - 1, 0) // 2
  ans.append(ans_a)
print(*ans, sep='\n')




### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

import collections

c = collections.Counter(A)

sum_all = sum([v * max(v - 1, 0) // 2 for k, v in c.items()])

ans = []
for a in A:
  b = c[a]
  ans_a = sum_all - (b * max(b - 1, 0) // 2) + (max(b - 1, 0) * max(b - 2, 0) // 2)
  ans.append(ans_a)
print(*ans, sep='\n')
### BUGGY CODE ###

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

l = [1]

flag = True

while flag:
    next = list_A[l[-1] - 1]

    if not next in l:
        l.append(next)

    else:
        start = l.index(next)
        roop = len(l) - start
        flag = False

if len(l) == 1:
    print(1)
    exit()

elif len(l) >= K:
    print(l[K])
    exit()

else:
    roop_remainder = (K + 1 - start) % roop
    if roop_remainder == 0:
        print(l[-1])
    else:
        print(l[start + roop_remainder -1])


### FIXED CODE ###

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

l = [1]
s = {1}

while True:
    next = list_A[l[-1] - 1]

    if not next in s:
        l.append(next)
        s.add(next)

    else:
        start = l.index(next)
        roop = len(l) - start
        break

if len(l) == 1:
    print(1)
    exit()

elif len(l) > K:
    print(l[K])
    exit()

else:
    roop_remainder = (K + 1 - start) % roop
    if roop_remainder == 0:
        print(l[-1])
    else:
        print(l[start + roop_remainder -1])
### BUGGY CODE ###

N = int(input())
l = list(map(int,input().split()))
#print(l,l[:1],l[1:])
ans = 100000000000000
s = sum(l)
for i in range(1,N):
  #print(sum(l[:i]),sum(l[i:]))
  #dif = abs(sum(l[:i])-sum(l[i:]))
  ans = min(ans, abs(s - 2*sum(l[i:])))
 
print(ans)

### FIXED CODE ###

N = int(input())
l = list(map(int,input().split()))
ans = 100000000000000
x = 0
S = sum(l)
for i in range(N-1):
  #print("l["+str(i)+"]="+str(l[0]))
  x = x + l[i]
  #print(x,S-x)
  ans = min(ans, abs(x - (S - x)))
  #print(ans)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))

dp = [[0] * (N + 1) for _ in range(N)]
for l in range(N):
  for r in range(l, N + 1):
    if l == r: continue
    if (N - (r - l)) % 2: dp[l][r] = float("inf")
    else: dp[l][r] = -float("inf") 
for c in range(N + 1):
  for l in range(N - c + 1):
    if l == N: continue
    r = l + c
    t = (N - (r - l)) % 2
    if l - 1 >= 0:
      if t == 0:
        dp[l - 1][r] = min(dp[l - 1][r], dp[l][r] - a[l - 1])
      else:
        dp[l - 1][r] = max(dp[l - 1][r], dp[l][r] + a[l - 1])
    if r + 1 <= N:
      if t == 0:
        dp[l][r + 1] = min(dp[l][r + 1], dp[l][r] - a[r])
      else:
        dp[l][r + 1] = max(dp[l][r + 1], dp[l][r] + a[r])
print(dp[0][N])

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
inf = 10 ** 14
dp = [[0] * (N + 1) for _ in range(N)]
for l in range(N):
  for r in range(l, N + 1):
    if l == r: continue
    if (N - (r - l)) % 2: dp[l][r] = inf
    else: dp[l][r] = -inf
for c in range(N + 1):
  for l in range(N - c + 1):
    if l == N: continue
    r = l + c
    t = (N - (r - l)) % 2
    if l - 1 >= 0:
      if t == 0:
        dp[l - 1][r] = min(dp[l - 1][r], dp[l][r] - a[l - 1])
      else:
        dp[l - 1][r] = max(dp[l - 1][r], dp[l][r] + a[l - 1])
    if r + 1 <= N:
      if t == 0:
        dp[l][r + 1] = min(dp[l][r + 1], dp[l][r] - a[r])
      else:
        dp[l][r + 1] = max(dp[l][r + 1], dp[l][r] + a[r])
print(dp[0][N])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
MOD = 10**9+7
N,K = map(int,input().split())
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)

ans = 1
def dfs(now, par,num):
    global ans
    ans = ans*num%MOD
    num = K-1
    if par != -1:
        num -= 1
    for ch in edge[now]:
        if ch != par:
            dfs(ch,now,num)
            num -= 1

dfs(0,-1,K)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
MOD = 10**9+7
N,K = map(int,input().split())
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)

ans = 1
def dfs(now, par,num):
    global ans
    ans = ans*num%MOD
    num = K-1
    if par != -1:
        num -= 1
    for ch in edge[now]:
        if ch != par:
            dfs(ch,now,num)
            num -= 1

dfs(0,-1,K)
print(ans)
### BUGGY CODE ###

n,ma,mb=map(int,input().split())
dp=[[[5000]*401for _ in range(401)] for _ in range(n+1)]
dp[0][0][0]=0
maa=mab=0
for i in range(1,n+1):
  a,b,c=map(int,input().split())
  maa+=a
  mab+=b
  for j in range(401):
    for k in range(401):dp[i][j][k]=min(dp[i-1][j][k],dp[i-1][j-a][k-b]+c)
ans=5000
for i in range(1,min(maa//ma,mab//mb)+1):
  if dp[n][ma*i][mb*i]!=5000:ans=min(ans,dp[n][ma*i][mb*i])
print(-1if ans==5000else ans)

### FIXED CODE ###

n,ma,mb=map(int,input().split())
dp=[[[5000]*401for _ in range(401)] for _ in range(n+1)]
dp[0][0][0]=0
maa=mab=0
for i in range(1,n+1):
  a,b,c=map(int,input().split())
  maa+=a
  mab+=b
  for j in range(401):
    for k in range(401):dp[i][j][k]=min(dp[i-1][j][k],dp[i-1][j-a][k-b]+c)
ans=5000
for i in range(1,min(maa//ma,mab//mb)+1):
  if dp[n][ma*i][mb*i]!=5000:ans=min(ans,dp[n][ma*i][mb*i])
print(-1if ans==5000else ans)
### BUGGY CODE ###

D,G = map(int, input().split())
L=[[0,0] for i in range(D)]

for i in range(D):
    L[i][0],L[i][1]=map(int, input().split())

MAP=[0]*(D+1)
i=0
a=10**10
while(MAP[-1]!=1):
    for j in range(D):
        if MAP[j] > L[j][0]:
            MAP[j] -= (L[j][0]+1)
            MAP[j+1]+=1 
    if(sum(MAP)<a):
        s=0
        for j in range(D):   
            s+=MAP[j]*(j+1)*100
            if(MAP[j] == L[j][0]):
                s+=L[j][1]
        if(s>=G):
            a=sum(MAP)
            #print(a,MAP)
    MAP[0]+=1

print(a)

### FIXED CODE ###

import math
D,G = map(int, input().split())
L=[[0,0] for i in range(D)]

for i in range(D):
    L[i][0],L[i][1]=map(int, input().split())
MAP=[0]*(D+1)
C=[[0,0] for i in range(D)]
for i in range(D):
    C[i][1]=(i+1)
    C[i][0]=L[i][0]*(i+1)*100
C=sorted(C,reverse=True)

a=10**10
while(MAP[-1]==0):
    for j in range(D):
        if MAP[j] > 1:
            MAP[j] -= 2
            MAP[j+1]+=1 
    s=0
    c=0
    for j in range(D):   
        if(MAP[j]!=0):
            s+=L[j][0]*(j+1)*100
            s+=L[j][1]
            c+=L[j][0]
    if(c<a):
        if(s<G):
            for i in range(D):
                if(MAP[C[i][1]-1]==0):
                    t=G-s
                    if(C[i][0]>t):
                        c+=math.ceil(t/(C[i][1]*100))
                        s+=C[i][1]*100*math.ceil(t/(C[i][1]*100))
                    break
        if(s>=G):
            a=min(a,c)
            #print(a,MAP)
    MAP[0]+=1
print(a)
### BUGGY CODE ###

import copy

# standart input
# n = int(input())
# a = list(map(int, input().split()))

N = 13
MOD = 10 ** 9 + 7

s = input()
rs = reversed(s)

dp = [0 for i in range(N)]
dp[0] = 1

for i, si in enumerate(rs):
    nextdp = [0 for i in range(N)]
    r = 10 ** i % N

    for j in range(10):
        jj = j
        if si == "?":
            pass
            # c = (j * 10 ** i) % N
        elif j == 0:
            jj = int(si)
        else:
            break

        for k in range(N):
            l = (k + r * jj) % N
            nextdp[l] = (nextdp[l] + dp[k]) % MOD

    dp = nextdp

print(dp[5])


### FIXED CODE ###

# standart input
# n = int(input())
# a = list(map(int, input().split()))

N = 13
MOD = 10 ** 9 + 7

s = input()[::-1]

dp = [0 for i in range(N)]
nextdp = [0 for i in range(N)]
zeros = [0 for i in range(N)]
dp[0] = 1

r = 1
for i, si in enumerate(s):
    nextdp = zeros[:]

    for j in range(10):
        jj = j
        if si == "?":
            pass
            # c = (j * 10 ** i) % N
        elif j == 0:
            jj = int(si)
        else:
            break

        for k in range(N):
            l = (k + r * jj) % N
            nextdp[l] = (nextdp[l] + dp[k]) % MOD

    dp = nextdp
    r = r * 10 % N

print(dp[5])
### BUGGY CODE ###

def main():
    n = int(input())
    tmpa = list(map(int, input().split()))
    a2 = [[0]*n for _ in range(n)]
    for i1 in range(n):
        for i2 in range(i1+1,n):
            if tmpa[i1] + tmpa[i2] == (i2 - i1):
                a2[i1][i2] = 1
    r = 0
    for row in a2:
        r += sum(row)
    print(r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter

def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnt = 0
    l1 = []
    for ea in a:
        l1.append(cnt - ea)
        cnt += 1
    l1c = Counter(l1)
    r = 0
    for i2 in range(n):
        r += l1c[i2 + a[i2]]
    print(int(r))

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

s = input()
s_len = len(s)
t = input()
t_len = len(t)
dp = [[0] * (t_len + 1) for _ in range(s_len + 1)]
for i in range(s_len):
    S = s[i]
    for j in range(t_len):
        T = t[j]
        ni = i + 1
        nj = j + 1
        if S == T:
            dp[ni][nj] = max(dp[ni][nj], dp[i][j] + 1, dp[i][nj], dp[ni][j])
        else:
            dp[ni][nj] = max(dp[ni][nj], dp[i][nj], dp[ni][j])

nagasa = dp[s_len][t_len]

a = s_len
b = t_len
ans = []
while nagasa > 0:
    if dp[a][b] == nagasa:
        a -= 1
    elif dp[a + 1][b] == nagasa:
        b -= 1
    else:
        ans.append(s[a])
        nagasa -= 1
ans = ans[::-1]
print(*ans, sep="")


### FIXED CODE ###

S=input()
T=input()
s=len(S)
t=len(T)
#dp[i][j] Sのi文字目までとTのj文字目までで最大共通文字数
dp=[[0]*(t+1) for i in range(s+1)]
for i in range(s):
    for j in range(t):
        if S[i]==T[j]:
            dp[i+1][j+1]=max(dp[i][j]+1, dp[i][j])
        else:
            dp[i+1][j+1]=max(dp[i+1][j], dp[i][j+1])
ans=''
while s>0 and t>0:
    if dp[s][t]==dp[s-1][t]:
        s-=1
    elif dp[s][t]==dp[s][t-1]:
        t-=1
    else:
        s-=1
        t-=1
        ans+=T[t]
ans=ans[::-1]
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

N, K = map(int,input().split())
MOD = 10**9+7

combination = [[-1]*(N+1) for i in range(N+1)]

def comb(n, k):
    if n < k:
        return 0
    elif k == n or k == 0:
        return 1
    elif k == 1:
        return n
    elif combination[n][k] != -1:
        return combination[n][k]
    else:
        combination[n][k] = (comb(n-1,k-1)+comb(n-1,k))%MOD
        return combination[n][k]

for i in range(1,K+1):
    print(comb(N-K+1,i)*comb(K-1,i-1)%MOD)
    

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

N, K = map(int,input().split())
MOD = 10**9+7

combination = [[-1]*(N+1) for i in range(N+1)]

def comb(n, k):
    if n < k:
        return 0
    elif k == n or k == 0:
        return 1
    elif k == 1:
        return n
    elif combination[n][k] != -1:
        return combination[n][k]
    else:
        combination[n][k] = (comb(n-1,k-1)+comb(n-1,k))%MOD
        return combination[n][k]

for i in range(1,K+1):
    print(comb(N-K+1,i)*comb(K-1,i-1)%MOD)