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

# -*- coding:utf-8 -*-
import sys


def solve():
    N, A = list(map(int, sys.stdin.readline().split()))
    Xs = list(map(int, sys.stdin.readline().split()))
    # dp[i][j][k] := 左からi枚目までに、j枚を選んで、選んだカードの総和がk  (iは0-origin)
    dp = [[[0]*(N*50+1) for _ in range(0, N+1)] for __ in range(0, N)]
    dp[0][0][0] = 1
    dp[0][1][Xs[0]] = 1

    for i in range(1, N):
        for j in range(0, N):
            for k in range(N*50+1):
                dp[i][j][k] += dp[i-1][j][k]
                if k+Xs[i] < N*50+1:
                    dp[i][j+1][k+Xs[i]] += dp[i-1][j][k]

    ans = 0
    for j in range(1, N+1):
        ans += dp[N-1][j][A*j]

    print(ans)


if __name__ == "__main__":
    solve()


### FIXED CODE ###

# -*- coding:utf-8 -*-
"""解説
dp[j][k][s] := x1,...,xjから k枚選んで xiの合計をsにするような選び方の総数

[@lilium氏]
https://atcoder.jp/contests/abc044/submissions/5887235
"""

def solve():
    N, A = list(map(int, input().split()))
    X = list(map(int, input().split()))

    max_x = max(X)
    dp = [[[0 for _ in range(4000+1)] for __ in range(N+1)] for ___ in range(N+1)]

    dp[0][0][0] = 1

    # dp[i][j][k] := i枚のうちj枚を選んで、和がkになる組み合わせ
    for i in range(N):
        for j in range(N):
            for k in range(4000+1):
                if dp[i][j][k] != 0:
                    dp[i+1][j][k] += dp[i][j][k]  # i枚目を選ばなかった
                    dp[i+1][j+1][k+X[i]] += dp[i][j][k]  # i枚目を選んだ

    ans = 0
    for j in range(1, N+1):
        ans += dp[N][j][j*A]
    print(ans)

if __name__ == "__main__":
    solve()
### BUGGY CODE ###

from decimal import Decimal
N,K=map(int,input().split())
ans = 0
for i in range(1,N+1):
    tmp = i
    t_k = 1
    while tmp < K:
        tmp = tmp*2
        t_k = t_k*2
    ans += Decimal(1/t_k)
print(Decimal(ans/N))

### FIXED CODE ###

from decimal import Decimal
N,K=map(int,input().split())
ans = 0
for i in range(1,N+1):
    if i >=K:
        ans+=N-i+1
        break
    tmp = i
    t_k = 1
    while tmp < K:
        tmp = tmp*2
        t_k = t_k*2
    ans += Decimal(1/t_k)
print(Decimal(ans/N))
### BUGGY CODE ###

from collections import*
_,s=open(0)
dp=defaultdict(bool)
for c in s[:-1]:
  for i in range(100):
    j=str(i).zfill(2)
    dp[j+c]|=dp[j]
  for i in range(10):
    j=str(i)
    dp[j+c]|=dp[j]
  dp[c]=True
print(sum(dp[str(i).zfill(3)]for i in range(1000)))

### FIXED CODE ###

_,s=open(0)
x,y,z=eval('set(),'*3)
for c in s[:-1]:
  for t in y:z.add(t+c)
  for t in x:y.add(t+c)
  x.add(c)
print(len(z))
### BUGGY CODE ###

from collections import defaultdict
from functools import reduce

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

MOD = 10 ** 9 + 7

def mul(a, b):
  return (a * b) % MOD

def power(x, y):
  if y == 0:
    return 1
  elif y == 1:
    return x % MOD
  elif y % 2 == 0:
    return power(x, y // 2) ** 2 % MOD
  else:
    return power(x, y // 2) ** 2 * x % MOD

def div(a, b):
  return mul(a, power(b, MOD - 2))

numer_cache = defaultdict(dict)
denom_inv_cache = {}

def numer(n, r):
  if r == 0:
    return 1
  numer_cache_n = numer_cache[n]
  if r not in numer_cache_n:
    numer_cache_n[r] = mul(numer(n, r - 1), n - r + 1)
  return numer_cache_n[r]

def denom_inv(r):
  if r == 0:
    return 1
  if r not in denom_inv_cache:
    denom_inv_cache[r] = div(denom_inv(r - 1), r)
  return denom_inv_cache[r]

def combinations_count(n, r):
  r = min(r, n - r)
  return mul(numer(n, r), denom_inv(r))

print(sum(mul(combinations_count(n, i), combinations_count(n - 1, i)) for i in range(min(n, k + 1))) % MOD)


### FIXED CODE ###

from collections import defaultdict
from functools import reduce

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

MOD = 10 ** 9 + 7

def mul(a, b):
  return a * b % MOD

def power(x, y):
  res = 1
  while True:
    if y & 1:
      res = res * x % MOD
    if y == 1:
      return res
    x = x * x % MOD
    y >>= 1

def div(a, b):
  return a * power(b, MOD - 2) % MOD

def dict1():
  return {0: 1}

numer_cache = defaultdict(dict1)
denom_inv_cache = dict1()

def combinations_count(n, r):
  r = min(r, n - r)
  numer_cache_n = numer_cache[n]
  if r not in numer_cache_n:
    numer_cache_n[r] = mul(numer_cache_n[r - 1], n - r + 1)
  if r not in denom_inv_cache:
    denom_inv_cache[r] = div(denom_inv_cache[r - 1], r)
  return mul(numer_cache_n[r], denom_inv_cache[r])

print(sum(mul(combinations_count(n, i), combinations_count(n - 1, i)) for i in range(min(n, k + 1))) % MOD)
### BUGGY CODE ###

import math
import copy
from copy import deepcopy
import sys
import fractions
# import numpy as np
from functools import reduce
# import statistics
import heapq
import collections
import itertools
sys.setrecursionlimit(100001)

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

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

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

data = []
input_data = input().split()
data = [int(n) for n in input_data]

ans = 0
for i in range(0, n-k+1, 1):
    exp_val = 0
    for j in range(k):
        exp_val += 1 + (data[i+j]-1)/2
    ans = max(ans, exp_val)

print(ans)




### FIXED CODE ###

import math
import copy
from copy import deepcopy
import sys
import fractions
# import numpy as np
from functools import reduce
# import statistics
import heapq
import collections
import itertools
sys.setrecursionlimit(100001)

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

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

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

data = []
input_data = input().split()
data = [int(n) for n in input_data]

data_exp = [0]
for i in range(n):
    data_exp.append(data_exp[i] + 1 + (data[i]-1)/2)

ans = 0
for i in range(n-k+1):
    tmp_ans = data_exp[i+k] - data_exp[i]
    ans = max(ans, tmp_ans)

print(ans)
### BUGGY CODE ###

from sys import stdin
import sys
# sys.setrecursionlimit(10**8)

def nextLine(): return next(stdin)
def nextStrList(): return nextLine().split()
def nextIntList(): return [int(_) for _ in nextStrList()]


def main():
	n=int(nextLine())
	aList=nextIntList()
	
	num=n//2
	score=[[None for _ in range(num)] for i in range(n)]
	
	for i in range(n):
		
		if i==0:
			score[i][0]=aList[i]
		else:
			score[i][0]=max(aList[i], score[i-1][0])
			
		for j in range(1, num):
			nextScore=[]
			if i>=1:
				s=score[i-1][j]
				if s is not None:
					nextScore.append(s)
			if i>=2:
				s=score[i-2][j-1]
				if s is not None:
					s+=aList[i]
					nextScore.append(s)
			if len(nextScore)>0:
				nextScore=max(nextScore)
				score[i][j]=nextScore
	
# 		print(i, *[str(s) for s in score[i]], sep="\t")
	
	print(score[-1][-1])
	
if __name__=="__main__":
	main()


### FIXED CODE ###

from sys import stdin
import sys
# sys.setrecursionlimit(10**8)

def nextLine(): return next(stdin)
def nextStrList(): return nextLine().split()
def nextIntList(): return [int(_) for _ in nextStrList()]

# def comp0(n, aList):
# 	num=n//2
# 	score=[[None for _ in range(num)] for i in range(n)]
# 	
# 	for i in range(n):
# 		
# 		if i==0:
# 			score[i][0]=aList[i]
# 		else:
# 			score[i][0]=max(aList[i], score[i-1][0])
# 			
# 		for j in range(1, num):
# 			nextScore=[]
# 			if i>=1:
# 				s=score[i-1][j]
# 				if s is not None:
# 					nextScore.append(s)
# 			if i>=2:
# 				s=score[i-2][j-1]
# 				if s is not None:
# 					s+=aList[i]
# 					nextScore.append(s)
# 			if len(nextScore)>0:
# 				nextScore=max(nextScore)
# 				score[i][j]=nextScore
# 	
# # 		print(i, aList[i], *[str(s) for s in score[i]], sep="\t")
# 	
# 	print(score[-1][-1])
	
	
def comp(n, aList):
	num=n//2
	score=[[None for _ in range(num)] for i in range(3)]
# 	base=[0 for _ in range(num)]
	
	for i in range(n):
		for j in range(max(0, num-(n-i)//2-1), min(i//2+1,num)):
			if j==0:
				if i==0:
					ns=aList[i]
				else:
					ns=max(aList[i], score[(i-1)%3][0])
			else:
				nextScore=[]
				if i>=1:
					s=score[(i-1)%3][j]
					if s is not None:
						nextScore.append(s)
				if i>=2:
					s=score[(i-2)%3][j-1]
					if s is not None:
						s+=aList[i]
						nextScore.append(s)
				if len(nextScore)>0:
					ns=max(nextScore)
			
			score[i%3][j]=ns
	
# 		print(i, *[str(s) for s in score[i%3]], sep="\t")
	
	print(score[(n-1)%3][-1])


def main():
	n=int(nextLine())
	aList=nextIntList()

# 	import numpy as np
# 	n=200000
# # 	aList=list(np.random.randint(-1000000000, 1000000001, n))
# # 	n=22
# 	aList=list(np.random.randint(-9, 10, n))
	
	comp(n, aList)
# 	comp0(n, aList)
	
	
if __name__=="__main__":
	main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
h,w = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
b = [list(map(int,input().split())) for i in range(h)]
grid = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w):
    grid[i][j] = abs(a[i][j]-b[i][j])
dp = [[[False for i in range(12881)] for j in range(w)] for k in range(h)]
for i in range(h):
  for j in range(w):
    for k in range(12801):
      t = grid[i][j]
      if i == j == 0 and t == k:
        dp[i][j][k] = True
      if j > 0:
        dp[i][j][k] = dp[i][j][k] or dp[i][j-1][k+t] or dp[i][j-1][abs(k-t)]
      if i > 0:
        dp[i][j][k] = dp[i][j][k] or dp[i-1][j][k+t] or dp[i-1][j][abs(k-t)]
for i in range(12801):
  if dp[h-1][w-1][i]:
    print(i)
    break


### FIXED CODE ###

h,w = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
b = [list(map(int,input().split())) for i in range(h)]
grid = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w):
    grid[i][j] = abs(a[i][j]-b[i][j])
dp = [[0 for j in range(w)] for k in range(h)]
buf = (h+w)*80
for i in range(h):
  for j in range(w):
      t = grid[i][j]
      if i == j == 0:
        dp[i][j] = 1 << buf+t | 1 << buf-t
      if j > 0:
        dp[i][j] = dp[i][j] | dp[i][j-1] << t | dp[i][j-1] >> t
      if i > 0:
        dp[i][j] = dp[i][j] | dp[i-1][j] << t | dp[i-1][j] >> t
for i in range(buf):
  if (dp[h-1][w-1] & 1 << buf+i) or (dp[h-1][w-1] & 1 << buf-i):
    print(i)
    exit()
### BUGGY CODE ###

N, M = map(int, input().split())
A = []
for i in range(N):
    a, b = map(int, input().split())
    A.append([a, b])
A = sorted(A, key = lambda x : x[0])
# print(A)
ans = 0

for i in range(M - 1, -1, -1):
    maximum_rwd = 0
    maximum_id = 0
    for j in range(len(A)):
        if A[j][0] > M - i:
            break
        # A[j]報酬までの時間、
        elif maximum_rwd < A[j][1]:
            maximum_id = j
            maximum_rwd = A[j][1]
    if maximum_rwd > 0:
        ans += maximum_rwd
        A.pop(maximum_id)
print(ans)

### FIXED CODE ###

import heapq

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

A = [[] for _ in range(M)]
Q = []

for _ in range(N):
	day, money = map(int, input().split())
	if day <= M:
		A[day - 1].append(money)

ans = 0

for i in range(0, M):
	for money in A[i]:
		heapq.heappush(Q, -money)
	# print(Q)
	if Q:
		ans += heapq.heappop(Q)
		
print(-ans)
### BUGGY CODE ###

n, q = map(int, input().split(' '))
s = input()
c = [0] * n
for i in range(1, n+1):
    c[i-1] = s[:i].count('AC')
for _ in range(q):
    l, r = map(int, input().split(' '))
    print(c[r-1] - c[l-1])


### FIXED CODE ###

n, q = map(int, input().split(' '))
s = input()
c = [0] * n
for i in range(1, n):
    c[i] += c[i-1]
    if s[i-1:i+1] == 'AC':
        c[i] += 1
for _ in range(q):
    l, r = map(int, input().split(' '))
    print(c[r-1] - c[l-1])
### BUGGY CODE ###

def addbit(i):
    i += 1
    while i <= N:
        BIT[i] += 1
        i += i & (-i)
def getsum(i):
    ret = 0
    i += 1
    while i != 0:
        ret += BIT[i]
        i -= i&(-i)
    return ret
def bit(L):
    global BIT
    BIT=[0] * (N+1)
    re = 0
    for l in L:
        re += getsum(l)
        addbit(l)
    return N*(N-1)//2 - re
def calc(Z):
    Z.sort()
    l, r, lc, rc = -1<<32, 1<<32, N*(N-1)//4, N*(N-1)//4
    f = 1
    while r - l > 0.000000001:
        m = (l+r) / 2 if f else (l * rc + r * lc) / (lc + rc)
        A = [a&((1<<16)-1) for a in sorted([(int((s*m+t)*2**40)<<16)+i for i, (s, t) in enumerate(Z)])]
        c = bit(A)
        if c > N*(N-1)//4:
            l = m
            lc = c - N*(N-1)//4
        else:
            r = m
            rc = max(N*(N-1)//4 - c, 1)
        
        f ^= 1
    return l

N = int(input())
X, Y = [], []
for _ in range(N):
    a, b, c = map(int, input().split())
    X.append((-a/b, c/b))
    Y.append((-b/a, c/a))
print(calc(X), calc(Y))


### FIXED CODE ###

def addbit(i):
    i += 1
    while i <= N:
        BIT[i] += 1
        i += i & (-i)
def getsum(i):
    ret = 0
    i += 1
    while i != 0:
        ret += BIT[i]
        i -= i&(-i)
    return ret
def bit(L):
    global BIT
    BIT=[0] * (N+1)
    re = 0
    for l in L:
        re += getsum(l)
        addbit(l)
    return N*(N-1)//2 - re
def calc(Z):
    Z.sort()
    l, r, lc, rc = -1<<28, 1<<28, N*(N-1)//4+1, N*(N-1)//4+1
    f = 1
    while (r - l) / max(abs(l), 1) > 0.000000001:
        m = (l+r) / 2 if f else (l * rc + r * lc) / (lc + rc)
        A = [a&((1<<16)-1) for a in sorted([(int((s*m+t)*2**40)<<16)+i for i, (s, t) in enumerate(Z)])]
        c = bit(A)
        if c > N*(N-1)//4:
            l = m
            lc = (c - N*(N-1)//4) * 2
        else:
            r = m
            rc = (N*(N-1)//4 - c) * 2 + 1
        f ^= 1
    return l

N = int(input())
X, Y = [], []
for _ in range(N):
    a, b, c = map(int, input().split())
    X.append((-a/b, c/b))
    Y.append((-b/a, c/a))
print(calc(X), calc(Y))
### BUGGY CODE ###

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

### FIXED CODE ###

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

n = int(input())
height = list(map(int, input().split()))
ans = 0
for i in range(n - 1):
    for j in range(i + 1 + height[i], n):
        if abs(j - i) == (height[i] + height[j]):
            ans += 1
print(ans)


### FIXED CODE ###

from collections import defaultdict
n = int(input())
height = list(map(int, input().split()))
add_set = defaultdict(int)
ans = 0
for i in range(n):
    add_set[i + height[i] + 1] += 1
    if i + 1 - height[i] in add_set:
        ans += add_set[i + 1 - height[i]]

print(ans)
### BUGGY CODE ###

import numpy as np
from collections import Counter

N = int(input())
A = np.array(list(map(int, input().split())))
B = np.arange(N) + 1

s = A + B
m = B - A

s_ct = Counter(s)
m_ct = Counter(m)

ans = 0
for i in s_ct:
    for j in m_ct:
        if i == j:
            ans += m_ct[j] * s_ct[i] 

print(ans)




### FIXED CODE ###

import numpy as np
from collections import Counter

N = int(input())
A = np.array(list(map(int, input().split())))
B = np.arange(N) + 1

s = A + B
m = B - A

s_ct = Counter(s)
m_ct = Counter(m)

ans = 0
for i in s_ct:
    ans += s_ct[i] * m_ct[i]

print(ans)
### BUGGY CODE ###

from collections import deque
import math

h, w = list(map(int, input().split()))
SHWs = [input() for i in range(h)]
#print(SHWs)


def bfs(sy, sx, gy, gx):
    visited = [[-1]*w for i in range(h)]
    visited[sy][sx] = 0
    que = deque([[sy, sx]])
    while que:
        
        y,x = que.popleft()
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            next_y, next_x = y+i, x+j
            # print(visited)
            if next_y < 0 or next_x < 0 or next_y > h-1 or next_x > w-1:
                continue
            if SHWs[next_y][next_x] == '.' and (visited[next_y][next_x] == -1 or visited[next_y][next_x] > visited[y][x]+1):
                visited[next_y][next_x] = visited[y][x] + 1
                que.append([next_y, next_x])
    
    return visited[gy][gx]

            
ans = 0
for sy in range(h):
    for sx in range(w):
        for gy in range(h):
            for gx in range(w):
                if sy == gy and sx == gx:
                    continue
                count = bfs(sy=sy, sx=sx, gy=gy, gx=gx) 
                if count > ans:
                    ans = count


print(ans)



### FIXED CODE ###

from collections import deque
import numpy as np
import math

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

def bfs(sy, sx):
    visited = [[-1]*w for i in range(h)]
    visited[sy][sx] = 0
    que = deque([[sy, sx]])
    while que:
        
        y,x = que.popleft()
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            next_y, next_x = y+i, x+j
            # print(visited)
            if next_y < 0 or next_x < 0 or next_y > h-1 or next_x > w-1:
                continue
            if SHWs[next_y][next_x] == '.' and (visited[next_y][next_x] == -1 or visited[next_y][next_x] > visited[y][x]+1):
                visited[next_y][next_x] = visited[y][x] + 1
                que.append([next_y, next_x])
    
    return np.amax(np.array(visited))

            
ans = 0
for sy in range(h):
    for sx in range(w):
        if SHWs[sy][sx] == '#':
            continue
        count = bfs(sy=sy, sx=sx)

        if count > ans:
            ans = count


print(ans)
### BUGGY CODE ###

#入力を受け取る
N,K=map(int,input().split())
a=list(map(int,input().split()))
#DPの配列(少し余裕を持たせる)、Falseで初期化
DP=[False]*(K+10)
for i in range(1,K+1):
    for j in range(N):
        if i-a[j]>=0:
            DP[i] |= ~DP[i-a[j]] # ~は否定の意味(ビット反転)
            #ORなので, 一つでもFalseがあればTrueがはいる
if DP[K]:print("First")
else: print("Second")

### FIXED CODE ###

#入力を受け取る
N,K=map(int,input().split())
a=list(map(int,input().split()))
#DPの配列(少し余裕を持たせる)、Falseで初期化
DP=[False]*(K+10)
for i in range(1,K+1):
    for j in range(N):
        if i-a[j]>=0:
            DP[i] |= ~DP[i-a[j]] # ~は否定の意味(ビット反転)
            #ORなので, 一つでもFalseがあればTrueがはいる
if DP[K]:print("First")
else: print("Second")
### BUGGY CODE ###

import sys
N = int(input())
list = list(map(int, input().split()))
  
for i in range(N):
  for j in range(N-i-1):
    if list[i] == list[j+i+1]:
      print("NO")
      sys.exit()
print("YES")

### FIXED CODE ###

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



if ((len(list)) == (len(set(list)))) == True:
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.extend([b]*e)
        b, e = b + 1, 0
    if n > 1:
        fct.extend([n]*1)
    return fct

N = int(input())
arr = factorize(N)
M = len(arr)
ans = N
for i in range(2**M):
    A = 1
    B = 1
    for j in range(M):
        if (i>>j)&1:
            A *= arr[j]
        else:
            B *= arr[j]
    A = max(A-1,0)
    B = max(B-1,0)
    ans = min(ans,A+B)

print(ans)

### FIXED CODE ###

import math
N = int(input())
tmp = math.ceil(N**(1/2))
ans = N
for i in range(1,tmp+1):
    if N%i == 0:
        A = max(N//i-1,0)
        B = max(i-1,0)
        ans = min(ans,A+B)

print(ans)
### BUGGY CODE ###

N = int(input())
C = [[] for i in range(N)]
for i in range(N):
  x, y = map(int, input().split())
  C[i] = [x, y, i]
Cx = sorted(C, key=lambda c: c[0])
Cy = sorted(C, key=lambda c: c[1])
Qx = sorted([[Cx[i + 1][0] - Cx[i][0], Cx[i][2], Cx[i + 1][2]] for i in range(N - 1)])
Qy = sorted([[Cy[i + 1][1] - Cy[i][1], Cy[i][2], Cy[i + 1][2]] for i in range(N - 1)])
R = [i for i in range(N)]
def root(n):
  if R[n] == n:
    return n
  else:
    R[n] = root(R[n])
    return R[n]
cnt = 0
cost = 0
x = 0
y = 0
while cnt < N - 1:
  if Qx[x][0] <= Qy[y][0]:
    q = Qx[x]
    x += 1
  else:
    q = Qy[y]
    y += 1
  if root(q[1]) != root(q[2]):
    R[R[q[2]]] = q[1]
    cost += q[0]
    cnt += 1
print(cost)

### FIXED CODE ###

N = int(input())
Cx = [[0, 0] for i in range(N)]
Cy = [[0, 0] for i in range(N)]
for i in range(N):
  x, y = map(int, input().split())
  Cx[i] = [x, i]
  Cy[i] = [y, i]
Cx.sort()
Cy.sort()
Qx = sorted([[Cx[i + 1][0] - Cx[i][0], Cx[i][1], Cx[i + 1][1]] for i in range(N - 1)])
Qy = sorted([[Cy[i + 1][0] - Cy[i][0], Cy[i][1], Cy[i + 1][1]] for i in range(N - 1)])
R = [i for i in range(N)]
def root(n):
  if R[n] == n:
    return n
  else:
    R[n] = root(R[n])
    return R[n]
cnt = 0
cost = 0
x = 0
y = 0
while cnt < N - 1:
  if Qx[x][0] <= Qy[y][0]:
    q = Qx[x]
    x += 1
  else:
    q = Qy[y]
    y += 1
  r1 = root(q[1])
  r2 = root(q[2])
  if r1 != r2:
    R[r2] = q[1]
    cost += q[0]
    cnt += 1
print(cost)
### BUGGY CODE ###

def main():
    N=int(input())
    S=input()
    ans=0
    for i in range(N-2):
        for j in range(i+1,N-1):
            lis=["R","G","B"]
            if S[i]!=S[j]:
                lis=["R","G","B"]
                lis.remove(S[i])
                lis.remove(S[j])
                k=S[j+1:].count(lis[0])
                ans=ans+k
            if j+(j-i)<N and S[i]!=S[j]:
                if S[j+(j-i)]!=S[i] and S[j+(j-i)]!=S[j]:
                    ans-=1
    print(ans)
 
main()


### FIXED CODE ###

def main():
    N=int(input())
    S=input()
    k1=S.count("R")
    k2=S.count("B")
    ans=k1*k2*(len(S)-k1-k2)
    for i in range(N-2):
        for j in range(i+1,N-1):
            if j+(j-i)<N and S[i]!=S[j]:
                if S[j+(j-i)]!=S[i] and S[j+(j-i)]!=S[j]:
                    ans-=1
    print(ans)
main()
### BUGGY CODE ###

N, X, Y = map(int, input().split())
count = [0] * (N-1)
for i in range(N):
    i += 1
    for j in range(N-i):
        j += i + 1
        if i < j:
            normal = j-i
            xtoy = abs(X-i) + 1 + abs(Y-j)
            ytox = abs(Y-i) + 1 + abs(X-j)
            minRoute = min([normal, xtoy, ytox])
            count[minRoute-1] += 1
for c in count:
    print(c)


### FIXED CODE ###

N, X, Y = map(int, input().split())
count = [0] * (N-1)
for i in range(N):
    i += 1
    for j in range(N-i):
        j += i + 1
        if i < j:
            normal = j-i
            xtoy = abs(X-i) + 1 + abs(Y-j)
            ytox = abs(Y-i) + 1 + abs(X-j)
            minRoute = min([normal, xtoy, ytox])
            count[minRoute-1] += 1
for c in count:
    print(c)
### BUGGY CODE ###

import sys
def input():
  return sys.stdin.readline()[:-1]

n = int(input())
a = list(map(int, input().split()))
b = set()

for i in range(n-1):
  if a[n-1-i]&1:
    b.add(n-i)
    for j in range(2, int((n-i)**0.5)+1):
      if (n-i)%j == 0:
        a[j-1] += 1
        if (n-i)//j != j:
          a[(n-i)//j -1] += 1
if a[0] != len(b)%2:
  b.add(1)
          
print(len(b))
if len(b)>0:
  print(*b)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = set()

for i in range(n-1):
  if a[n-1-i]&1:
    b.add(n-i)
    for j in range(2, int((n-i)**0.5)+1):
      if (n-i)%j == 0:
        a[j-1] += 1
        if (n-i)//j != j:
          a[(n-i)//j -1] += 1
if a[0] != len(b)%2:
  b.add(1)
          
print(len(b))
if len(b)>0:
  print(*b)