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

import sys, re, os
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

h, w, k = MAP()
s = [[int(i) for i in STR()] for _ in range(h)]

ans = inf
for i in range(2 ** (h - 1)): #縦方向の割り方を全探索
    hdiv = [1 for _ in range(h)]
    for j in range(h - 1):
        tmp = 2 ** j
        hdiv[j] = 1 if i & tmp else 0
    sh = sum(hdiv)
    tmpans = sh - 1
    wdiv = [0 for _ in range(w - 1)]
    partsum = [0 for _ in range(sh + 1)]
    j = 0
    while j < w:
        tmp = 0
        idx = 0
        for kk in range(h):
            tmp += s[kk][j]
            if hdiv[kk]:
                partsum[idx] += tmp
                tmp = 0
                idx += 1
        flag = True
        for kk in range(sh + 1):
            if partsum[kk] > k:
                tmpans += 1
                partsum = [0 for _ in range(sh + 1)]
                flag = False
        if flag:
            j += 1
    ans = min(ans, tmpans)
print(ans)

### FIXED CODE ###

import sys
inf = sys.maxsize

if __name__ == '__main__':
    h, w, k = map(int, sys.stdin.readline().strip().split())
    s = [[int(i) for i in sys.stdin.readline().strip()] for _ in range(h)]
    
    ans = inf
    for i in range(2 ** (h - 1)): #縦方向の割り方を全探索 O(512)
        hdiv = [1 if i & 2 ** j else 0 for j in range(h - 1)]
        hdiv.append(1)
        sh = sum(hdiv)
        tmpans = sh - 1
        partsum = [0 for _ in range(sh)]
        partsum_p = [0 for _ in range(sh)]
        j = 0
        for j in range(w): #O(10 ** 3)
            tmp = 0
            idx = 0
            flag = False
            for kk in range(h): #O(10)
                tmp += s[kk][j]
                if hdiv[kk]:
                    partsum_p[idx] = partsum[idx]
                    partsum[idx] += tmp
                    if partsum[idx] > k and not flag:
                        tmpans += 1
                        flag = True
                    tmp = 0
                    idx += 1
            if flag:
                partsum = [partsum[l] - partsum_p[l] for l in range(sh)]
                partsum_p = [0 for _ in range(sh)]
                for kk in range(sh):
                    if partsum[kk] > k:
                        tmpans = inf
                        break
        ans = min(ans, tmpans)
    print(ans)
### BUGGY CODE ###

def main():
    S = input()
    div = pow(10, 9) + 7
    rem = [0 for _ in range(13)]
    rem[0] = 1
    for c in S:
        temp = [0 for _ in range(13)]
        if c != "?":
            for i in range(13):
                r = (i*10+int(c)) % 13
                temp[r] += rem[i]
        else:
            for i in range(13):
                for j in range(10):
                    r = (i*10+j) % 13
                    temp[r] += rem[i]
        rem = temp
    return rem[5] % div

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

def main():
    S = input()
    div = pow(10, 9) + 7
    rem = [0 for _ in range(13)]
    rem[0] = 1
    for c in S:
        temp = [0 for _ in range(13)]
        if c != "?":
            for i in range(13):
                r = (i*10+int(c)) % 13
                temp[r] += rem[i] % div
        else:
            for i in range(13):
                for j in range(10):
                    r = (i*10+j) % 13
                    temp[r] += rem[i] % div
        rem = temp
    return rem[5] % div

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

import collections
N = int(input())
A = list(map(int, input().split()))
for x in range(N):
  ans = 0
  b = A.pop(x)
  #print(A)
  c = collections.Counter(A)
  #print(c)
  v = [k for j,k in c.items()]
  #print(v)
  for i in v:
    ans += i*(i-1)//2
  print(ans)
  A.insert(x,b)

### FIXED CODE ###

from collections import Counter

n = int(input())
a = [int(x) for x in input().split()]
s = 0
c = Counter(a)
# print(c)
for i in c.values():
    s += i*(i-1)// 2
    
# print(s)
for j in range(n):
    t = c[a[j]]
    print(s-t+1)
### BUGGY CODE ###

n,k=map(int,input().split())
if n<k:
  print(1)
  exit()
for i in range (n):
  if k**i < n <k**(i+1):
    print(i+1)

### FIXED CODE ###

n,k=map(int,input().split())
ans=0
while n>0:
  n = n//k
  ans +=1
print(ans)
### BUGGY CODE ###

n = int(input())
d = []
for i in range(n):
    op = input().split()
    if op[0] == 'insert':
        d.append(op[1])  
    elif op[0] == 'find':
        if op[1] in d:
            print('yes')
        else:
            print('no')

### FIXED CODE ###

import sys
n = int(input())
d = {}
for op in sys.stdin.readlines():
    op = op.split()
    if op[0] == 'insert':
        d[op[1]] = 1  
    elif op[0] == 'find':
        if op[1] in d:
            print('yes')
        else:
            print('no')
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def is_reachable(adj, s, t):
    d = BFS(adj, s)
    if d[t] != -1:
        return True
    else:
        return False

def BFS(adj, start):
    n = len(adj)
    d = [-1] * n
    flag = [0] * n
    Q = []

    Q.append(start)
    d[start] = 0
    flag[start] = 1

    while len(Q) != 0:
        u = Q.pop(0)
        v = [i for i, x in enumerate(adj[u]) if (x == 1) and (flag[i] == 0)] # v := ??£??\???????????????????????¢?´¢??????????????????
        
        for i in v:
            Q.append(i)
            d[i] = d[u] + 1
            flag[i] = 1
    
    return d

def main():
    
    n, m = list(map(int, input().split()))
    adj = [[0 for i in range(n)] for j in range(n)]

    for i in range(m):
        s, t = list(map(int, input().split()))
        adj[s][t] = 1
        adj[t][s] = 1
    q = int(input())
    
    for i in range(q):
        s, t = list(map(int, input().split()))
        if is_reachable(adj, s, t):
            print("yes")
        else:
            print("no")
        
if __name__ == "__main__":
    main()    

### FIXED CODE ###

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

def assignColor():
    for i in range(n):
        if C[i] == -1:
            DFS(i)

#@profile
def DFS(start):
    S = [start]
    C[start] = start
    while len(S) != 0:
        u = S.pop(0)
        for i in adj_list[u]:
            if C[i] == -1:
                C[i] = start
                S.append(i)

if __name__ == "__main__":
    _input = sys.stdin.readlines()
    n, m = list(map(int, _input[0].split()))
    adj_list = [[] for i in range(n)]
    C = [-1] * n
    
    for i in range(m):
        s, t = list(map(int, _input[i+1].split()))
        adj_list[s].append(t)
        adj_list[t].append(s)
    assignColor()
    q = int(_input[m+1])
    for i in range(q):
        s, t = list(map(int, _input[m+i+2].split()))
        if C[s] == C[t]:
            print("yes")
        else:
            print("no")
### BUGGY CODE ###

N, K = map(int, input().split())
sushi = [tuple(map(int, input().split())) for i in range(N)]
point = [0 for i in range(K+1)]

sushi.sort(key=lambda x: x[1], reverse=True)

eaten_sushi = [sushi[i] for i in range(K)]
eaten_variation = [s[0] for s in eaten_sushi]
variation_number = len(set(eaten_variation))
base = sum([s[1] for s in eaten_sushi])
bonus = variation_number ** 2
point[variation_number] = base + bonus


for i in range(K, N):
    if sushi[i][0] in eaten_variation:
        continue

    for j in range(K-1, 0, -1):
        if eaten_variation.count(eaten_sushi[j][0]) == 1:
            continue
        base = base - sushi[j][1] + sushi[i][1]
        eaten_sushi.pop(j)
        eaten_sushi.append(sushi[i])
        eaten_variation.pop(j)
        eaten_variation.append(sushi[i][0])
        variation_number += 1
        bonus = variation_number ** 2
        point[variation_number] = base + bonus
        break

print(max(point))


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import defaultdict
from itertools import accumulate
import heapq

def solve(N: int, K: int, t: "List[int]", d: "List[int]"):
    sushi = defaultdict(list)
    for i in range(N):
        sushi[t[i]].append(d[i])

    A = [] # 各ネタでいちばんおいしい寿司のおいしさ
    B = [] # 各ネタで2番目以降においしい寿司のおいしさリスト
    
    for v in sushi.values():
        v.sort(reverse=True)
        A.append(v[0])
        B.extend(v[1:])
    A.sort(reverse=True)
    B.sort(reverse=True)

    X = [0] + [x for x in accumulate(A)] # X[i]: Aからうまい順にi個選んだ時のおいしさ合計
    Y = [0] + [y for y in accumulate(B)] # Y[j]: Bからうまい順にj個選んだ時のおいしさ合計

    res = 0
    for i in range(1, min(len(X), K + 1)):
        if K - i < len(Y):
            res = max(res, X[i] + Y[K - i] + i ** 2) 
            # B[:i]に含まれるネタが、A[i+1:]に含まれていた場合、実際のネタ数はiより多いが、
            # その場合はiを多くとったほうが、より美味しさが大きくなる。
            # そのためres[i]が答えになりえないため、無視して良い。
    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    K = int(next(tokens))  # type: int
    t = [int()] * (N)  # type: "List[int]" 
    d = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        t[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, K, t, d)

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

# C - GeT AC
N, Q = map(int, input().split())
S = str(input())
A = [list(map(int, input().split())) for i in range(Q)]

for i in range(Q):
    count = 0
    for j in range(A[i][0]-1,A[i][1]-1):
        if S[j] == 'A' and S[j+1] == 'C':
            count += 1
        else:
            pass
    print(count)

### FIXED CODE ###

# C - GeT AC
N, Q = map(int, input().split())
S = str(input())
A = [list(map(int, input().split())) for i in range(Q)]
S1 = [0]*N
count = 0
for j in range(1,len(S)):
    if S[j] == 'C' and S[j - 1] == 'A':
        count += 1
    else:
        pass
    S1[j] = count
#print(S1)

for k in range(Q):
    print(S1[A[k][1]-1]-S1[A[k][0]-1])
### BUGGY CODE ###

def main():
    n = int(input())
    s = list(input())
    sr = [0] * n
    sg = [0] * n
    sb = [0] * n
    for i1 in range(n):
        ts = s[i1]
        if ts == 'R':
            sr[i1] = 1
        elif ts == 'G':
            sg[i1] = 1
        else:
            sb[i1] = 1
    if n <= 3:
        print(0)
        exit()
    r = 0
    for ia in range(0,n-3):
        ta = s[ia]
        for ib in range(ia+1, n-1):
            tb = s[ib]
            t = (ta, tb)
            sa = ib - ia
            if ta == tb:
                pass
            else:
                if 'R' in t and 'G' in t:
                    r += sum(sb[ib+1:])
                    if ib + sa < n:
                        r -= sb[ib + sa]
                elif 'G' in t and 'B' in t:
                    r += sum(sr[ib+1:])
                    if ib + sa < n:
                        r -= sr[ib + sa]
                else:
                    r += sum(sg[ib + 1:])
                    if ib + sa < n:
                        r -= sg[ib + sa]

    print(r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    s = list(input())
    sr = [0] * n
    sg = [0] * n
    sb = [0] * n
    for i1 in range(n):
        ts = s[i1]
        if ts == 'R':
            sr[i1] = 1
        elif ts == 'G':
            sg[i1] = 1
        else:
            sb[i1] = 1
    if n <= 3:
        print(0)
        exit()
    r = 0
    for ia in range(0,n-3):
        ta = s[ia]
        if ta == 'R':
            r += sum(sg[ia+1:]) * sum(sb[ia+1:])
        elif ta == 'G':
            r += sum(sr[ia+1:]) * sum(sb[ia+1:])
        else:
            r += sum(sg[ia + 1:]) * sum(sr[ia + 1:])
        for ib in range((n - ia)//2+1):
            if ia + ib * 2 < n:
                if ta != s[ia + ib] and ta != s[ia + ib + ib] and s[ia+ib]!= s[ia + ib + ib]:
                    r -= 1
    print(r)

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

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

def F2_GaussJordan(A, is_extended = False):
    rank = 0
    for col in range(len(A[0])):
        if (is_extended and col == len(A[0])-1):
            break
        pivot = -1
        for row in range(rank,len(A)):
            if A[row][col]:
                pivot = row
                break
        if pivot == -1: 
            continue
        A[pivot],A[rank] = A[rank],A[pivot]
        for row in range(rank+1,len(A)):
            if A[row][col]:
                A[row] = [A[row][j]^A[rank][j] for j in range(len(A[0]))]
        rank += 1
    return A

N = I()
A = III()

xor = 0
for i in range(N):
    xor ^= A[i]

max_digit = len(format(max(A), 'b'))

use_digit = []
ans = 0
for j in range(max_digit)[::-1]:
    if xor>>j & 1:
        ans += 2**j
    else:
        use_digit.append(j)

a = [[0]*len(use_digit) for _ in range(N)]
k = 0
for k,j in enumerate(use_digit):
    for i in range(N):
        if A[i]>>j & 1:
            a[i][k] = 1

g = F2_GaussJordan(a,False)

s = 0
for i in range(N):
    s = max(s,s^sum([g[i][j]*2**use_digit[j] for j in range(len(use_digit))]))
ans += 2*s

print(ans)

### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N = I()
A = III()

xor = 0
for i in range(N):
    xor ^= A[i]

for i in range(N):
    A[i] &= ~xor

max_digit = len(format(max(A), 'b'))
rank = 0
for col in range(max_digit)[::-1]:
    pivot = -1
    for row in range(rank,N):
        if A[row]>>col & 1:
            pivot = row
            break
    if pivot == -1: 
        continue
    A[pivot],A[rank] = A[rank],A[pivot]
    for row in range(rank+1,N):
        if A[row]>>col & 1:
            A[row] ^= A[rank]
    rank += 1

val = 0
for i in range(N):
    val = max(val,val^A[i])

print(2*val + xor)
### BUGGY CODE ###

N,M=map(int, input().split())
A=list(map(int, input().split()))
B=[0]*M
C=[0]*M
for i in range(M):
  B[i],C[i] = map(int, input().split())

A_sort = A.sort()

for i in range(N):
  if len(C)==0:
    break
  Cmax = max(C)
  if A[i]<Cmax:
    A[i] = Cmax
    index = max(enumerate(C), key=lambda x: x[1])[0]
    B[index] -= 1
    if B[index] == 0:
      B.pop(index)
      C.pop(index)
print(sum(A))

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

N,M = II()
A = III()
B,C = Line(M)

a = []
for i in range(N):
  a.append([1,A[i]])
for i in range(M):
  a.append([B[i],C[i]])

a.sort(key=lambda x:x[1],reverse=True)
#a.sort(key=lambda x:-x[1])
counter = 0
ans = 0

for i in range(N+M):
  if counter + a[i][0] >= N:
    ans += a[i][1]*(N-counter)
    break
  else:
    counter += a[i][0]
    ans += a[i][1]*a[i][0]

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

n = input()
cnt = 0
for i in range(0,len(n)-3):
    for j in range(i+3,len(n)):
        if int(n[i:j+1])%2019 == 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

num = [0 for i in range(2019)]
num[0] = 1
count = 0
s = input()
now = 0
p = 1
for i in range(len(s) - 1, -1, -1):
    now = (now + int(s[i]) * p) % 2019
    count += num[now]
    num[now] += 1
    p = p * 10 % 2019
print(count)
### BUGGY CODE ###

N=int(input())
if N==1:
  print(0)
  exit(0)
a=[i for i in range(1,N)]
print(sum(a))

### FIXED CODE ###

N=int(input())
if N==1:
  print(0)
  exit(0)
#a=[i for i in range(1,N)]
#print(sum(a))
if (N-1)%2==0:
  print(N*((N-1)//2))
else:
  print(N*((N-1)//2)+((N-1)//2)+1)
### BUGGY CODE ###

N = int(input())
c = 0
for i in range(1,N):
  for j in range(1,N):
    if i*j >= N:
      break
    c += 1
print(c)

### FIXED CODE ###

N = int(input())
c = 0
for i in range(1,N):
  if i**2 >= N:
    break
  c += 1
for i in range(1,N):
  for j in range(i+1,N):
    if i*j >= N:
      break
    c += 2
print(c)
### BUGGY CODE ###

def change(S,index,color):
	lstS = list(S)
	lstS[index] = color
	S = ''.join(lstS)

	return S


if __name__ == '__main__':
	N = int(input())
	S = input()
	L = 0
	R = N-1
	count = 0
	if S.count('W') == 0 or S.count('R') == 0:
		R = -1
	while(L < R):
		while(S[L] == 'R'):
			L += 1
		while(S[R] == 'W'):
			R -= 1
		if L > R:
			break
		S = change(S,L,'R')
		S = change(S,R,'W')
		L += 1
		R -= 1
		count += 1

	print(count)

### FIXED CODE ###

if __name__ == '__main__':
	N = int(input())
	S = input()
	L = 0
	R = N-1
	count = 0
	if S.count('W') == 0 or S.count('R') == 0:
		R = -1
	while(L < R):
		while(S[L] == 'R'):
			L += 1
		while(S[R] == 'W'):
			R -= 1
		if L > R:
			break
		L += 1
		R -= 1
		count += 1

	print(count)
### BUGGY CODE ###

n= int(input())
a = list(map(int, input().split()))
g = [[0]*20 for i in range(n)]
for i in range(n):
  e = a[i]
  for j in range(20):
    g[i][j]+=e%2
    e//=2
ans=n
for i in range(n-1):
  b = a[i]
  c = g[i]
  for j in range(i+1,n):
    b+=a[j]
    d=0
    for k in range(20):
      c[k]+=g[j][k]
      d+=(2**k)*(c[k]%2)
    if b==d:
      ans+=1
print(ans)

### FIXED CODE ###

n= int(input())
a = list(map(int, input().split()))
g = [[0]*20 for i in range(n)]
for i in range(n):
  e = a[i]
  for j in range(20):
    g[i][j]+=e%2
    e//=2
ans=0
b =0
c =0
d= [0]*20
s=1
while(1):
  e =0
  if s ==1:
    for i in range(20):
      d[i]+=g[c][i]
      if d[i]>=2:
        e+=1
  else:
    for i in range(20):
      d[i]-=g[b-1][i]
      if d[i]>=2:
        e+=1
  if e==0 and c!=n-1:
    s=1
    c+=1
  elif e!=0:
    ans+=c-b
    s=0
    b+=1
  else:
    ans+=c-b+1
    s=0
    b+=1
    if b==n:
      break
print(ans)
### BUGGY CODE ###

import itertools
n = int(input())
l = list(map(int,input().split()))
c = [i for i in itertools.combinations(l,3) if i[0]<i[1]+i[2] and i[1]<i[2]+i[0] and i[2]<i[0]+i[1]]
print(len(c))

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
for b in range(n):
  for a in range(b):
    ans += bisect.bisect_left(l,l[a]+l[b])-(b+1)
print(ans)
### BUGGY CODE ###

n = int(input())
x = input().split()
a = 0
b = 1
while a <= n - 1 :
  b = b * int(x[a])
  a += 1
if b <= 1000000000000000000:
  print(b)
else:
  print(-1)

### FIXED CODE ###

n = int(input())
x = input().split()
a = 0
b = 1
if x.count('0') >= 1:
  print(0)
else:
  while a <= n - 1 and b <= 1000000000000000000:
    b = b * int(x[a])
    a += 1
  if b > 1000000000000000000:
    print(-1)
  else:
    print(b)
### BUGGY CODE ###

n = int(input())
print(sum(i for i in range(n)))

### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

n, m = map(int, input().split())
ps_list = [[i for i in input().split()] for j in range(m)]

ac_list = [0 for i in range(n)]
wa_list = [0 for i in range(n)]
num_wa = 0
num_ac = 0

for ps in ps_list:
    p = int(ps[0])
    s = ps[1]
    
    if s == 'AC' and not ac_list[p-1]:
        ac_list[p-1] = 1
        num_wa += wa_list[p-1]
        num_ac += 1
    elif p not in ac_list:
        wa_list[p-1] += 1
        
print(num_ac, num_wa)

### FIXED CODE ###

n, m = map(int, input().split())
ps_list = [[i for i in input().split()] for j in range(m)]

ac_list = []
wa_list = [0 for i in range(n)]
num_wa = 0
num_ac = 0

for ps in ps_list:
    p = int(ps[0])
    s = ps[1]
    
    if s == 'AC' and wa_list[p-1] != -1:
        ac_list.append(p)
        num_wa += wa_list[p-1]
        num_ac += 1
        wa_list[p-1] = -1
    elif wa_list[p-1] != -1:
        wa_list[p-1] += 1
        
print(num_ac, num_wa)
### BUGGY CODE ###

import sys
import copy

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

SC=[0,0,0,0]#0個,1個,2個,3個

for a in A:
    SC[a]+=1
SC=tuple(SC)

DP=dict()
DP[SC]=[1,0]#遷移確率0,経過日数

def plus(A,B):
    xa,ya=A
    xb,yb=B

    x=xa+xb
    y=(xa*ya+xb*yb)/(xa+xb)
    return [x,y]
#print(DP)
while True:
    NEXT=dict()
    
    for a,b,c,d in DP:
        x,y=DP[(a,b,c,d)]
        

        #print(a,b,c,d,x,y)
        #print(NEXT.get((a+1,b-1,c,d),[0,0]),[x*b/(b+c+d),y+N/(b+c+d)])

        if b>0:
            NEXT[(a+1,b-1,c,d)]=plus(NEXT.get((a+1,b-1,c,d),[0,0]),[x*b/(b+c+d),y+N/(b+c+d)])

        if c>0:
            NEXT[(a,b+1,c-1,d)]=plus(NEXT.get((a,b+1,c-1,d),[0,0]),[x*c/(b+c+d),y+N/(b+c+d)])

        if d>0:
            NEXT[(a,b,c+1,d-1)]=plus(NEXT.get((a,b,c+1,d-1),[0,0]),[x*d/(b+c+d),y+N/(b+c+d)])

        #print(NEXT)

    DP=copy.deepcopy(NEXT)

    #print(DP)

    if len(DP)==1:
        a,b,c,d=list(DP.keys())[0]
        if b==c==d==0:
            print(DP[(a,b,c,d)][1])
            sys.exit()


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

SC=[0,0,0]#1個,2個,3個

for a in A:
    SC[a-1]+=1
one,two,three=SC

DAYSDICT=[[[0.0]*301 for j in range(301)] for k in range(301)]
DAYSDICT[0][0][0]=0
def days(one,two,three):
    ANS=N
    if one>0:
        ANS+=DAYSDICT[one-1][two][three]*one
    if two>0:
        ANS+=DAYSDICT[one+1][two-1][three]*two
    if three>0:
        ANS+=DAYSDICT[one][two+1][three-1]*three
        
    DAYSDICT[one][two][three]=ANS/(one+two+three)


for k in range(three+1):
    for j in range(two+three+1-k):
        for i in range(one+two+three+1-j-k):
            if i==j==k==0:
                continue
            days(i,j,k)

print(DAYSDICT[one][two][three])