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

h,w = map(int,input().split())
tate = [[0]*w for i in range(h)]
yoko = [[0]*w for i in range(h)]
s = [str(input()) for i in range(h)]

for i in range(h):
    cnt = 0
    now = 0
    for j in range(w):
        if s[i][j] == ".":
            cnt += 1
        else:
            for k in range(now,j+1):
                yoko[i][k] = cnt
            cnt = 0
            now = j+1
    for k in range(now,j+1):
        yoko[i][k] = cnt
for i in range(w):
    cnt = 0
    now = 0
    for j in range(h):
        if s[j][i] == ".":
            cnt += 1
        else:
            for k in range(now,j):
                tate[k][i] = cnt
            cnt = 0
            now = j+1
    for k in range(now,j+1):
        tate[k][i] = cnt
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans,tate[i][j]+yoko[i][j]-1)
print(ans)

### FIXED CODE ###

h,w = map(int,input().split())
tate = [[0]*w for i in range(h)]
yoko = [[0]*w for i in range(h)]
s = [str(input()) for i in range(h)]

for i in range(h):
    cnt = 0
    now = 0
    for j in range(w):
        if s[i][j] == ".":
            cnt += 1
        else:
            for k in range(now,j+1):
                yoko[i][k] = cnt
            cnt = 0
            now = j+1
    for k in range(now,j+1):
        yoko[i][k] = cnt
for i in range(w):
    cnt = 0
    now = 0
    for j in range(h):
        if s[j][i] == ".":
            cnt += 1
        else:
            for k in range(now,j):
                tate[k][i] = cnt
            cnt = 0
            now = j+1
    for k in range(now,j+1):
        tate[k][i] = cnt
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans,tate[i][j]+yoko[i][j]-1)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
from collections import deque


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

def bfs(sx,sy,gx,gy):
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    d = [[float('inf')]*w for i in range(h)]
    q = deque()
    q.append((sx,sy))
    d[sx][sy] = 0
    while q:
        x,y = q.popleft()
        if x == gx and y == gy:
            break
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if  0<= nx < h and 0 <= ny < w and d[nx][ny]==float('inf') and s[nx][ny]=='.':
                q.append((nx,ny))
                d[nx][ny] = d[x][y]+1
    return d[gx][gy]

count = 0
for i in range(h):
    for j in range(w):
        for k in range(h):
            for l in range(w):
                if s[i][j] != '#' and s[k][l] != '#':
                    count  = max(count, bfs(i,j,k,l))
print(count)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
from collections import deque


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

def bfs(sx,sy):
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    d = [[-1]*w for i in range(h)]
    q = deque()
    q.append((sx,sy))
    d[sx][sy] = 0
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if  0<= nx < h and 0 <= ny < w and d[nx][ny]==-1 and s[nx][ny]=='.':
                q.append((nx,ny))
                d[nx][ny] = d[x][y]+1
    return max([max(i) for i in d])

count = 0
for i in range(h):
    for j in range(w):
        if s[i][j] != '#':
            count  = max(count, bfs(i,j))
print(count)
### BUGGY CODE ###

n = int(input())
s = [ input() for _ in range(n) ]

d = {}
for ss in s:
    d[ss] = d.get(ss, 0) + 1

t = set([ ss for ss in s if d[ss] == max(d.values())])
print("\n".join( sorted(list(t)) ))

### FIXED CODE ###

n = int(input())
s = [ input() for _ in range(n) ]

d = {}
for ss in s:
    d[ss] = d.get(ss, 0) + 1

maxi = max(d.values())
t = list(set([ ss for ss in s if d[ss] == maxi]))
t.sort()
print("\n".join(t))
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
max_p = 0
ans_index = 0

total = [0]
for i in range(1, 20000):
    total.append(total[i-1]+i)

for i in range(n-k+1):
    tmp = sum(p[i:i+k])
    if tmp > max_p:
        max_p = tmp
        ans_index = i
ans = 0
for i in range(k):
    ans += total[p[ans_index+i]] / p[ans_index+i]
print(ans)


### FIXED CODE ###

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

total = [0]
for i in range(1, 200000):
    total.append(total[i-1]+i)

ans_index = 0
cur = sum(p[0:k])
max_p = cur
for i in range(n-k+1):
    cur = cur + p[i+k-1] - p[i-1]
    if cur > max_p:
        max_p = cur
        ans_index = i
ans = 0
for i in range(k):
    ans += total[p[ans_index+i]] / p[ans_index+i]
print(ans)
### BUGGY CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        ki = int(K[i])
        for j in range(2):
            uki = 9 if j else ki
            dpij = dp[i][j]
            dpi1 = dp[i + 1]
            for d in range(D):
                for k in range(uki + 1):
                    dpi1j_ = dpi1[j or k < ki]
                    d_ = (d + k) % D
                    dpi1j_[d_] += dpij[d]
                    if dpi1j_[d_] > mod:
                        dpi1j_[d_] -= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f(K, D))


### FIXED CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        ki = int(K[i])
        for j in range(2):
            uki = 9 if j else ki
            dpij = dp[i][j]
            for d in range(D):
                for k in range(uki + 1):
                    dpij_ = dp[i + 1][j or k < ki]
                    d_ = (d + k) % D
                    dpij_[d_] += dpij[d]
                    dpij_[d_] %= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f(K, D))
### BUGGY CODE ###

def main():
    N = int(input())
    ABCD = [list(map(int, input().split())) for i in range(N)]
    for A,B,C,D in ABCD:
        # 在庫が買う本数以下 or 在庫追加が買う本数以下
        if A < B or D < B:
            print("No")
            continue

        A %= B
        # 在庫が買う本数以下になり、補給出来ない
        if C < A:
            print("No")
            continue
        if B == D:
            print("Yes")
            continue

        tmp = D-B
        flag = True
        for i in range(C+1,B):
            if (i-A) % tmp == 0:
                flag = False
                break
        print("Yes" if flag else "No")


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import math

    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(input())
    ABCD = [list(map(int, input().split())) for i in range(N)]
    for A,B,C,D in ABCD:
        # 在庫が買う本数以下 or 在庫追加が買う本数以下
        if A < B or D < B:
            print("No")
            continue

        A %= B
        # 在庫が買う本数以下になり、補給出来ない
        if C < A:
            print("No")
            continue
        if B == D:
            print("Yes")
            continue

        flag = True
        #print((B-A-1)%(D-B) ,">", (B-1)-(C+1))
        if (B-A-1)%(gcd(D,B)) <= (B-1)-(C+1):
            flag = False
        
        print("Yes" if flag else "No")


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

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

dp = [[0.] * (N+1) for _ in range(N+1)]
dp[0][0] = 1.

for i in range(1, N+1):
    for j in range(i+1):
        prob = dp[i-1][j-1]*p[i-1]
        if i > 0:
            prob += dp[i-1][j]*(1.-p[i-1])
        dp[i][j] = max(dp[i][j], prob)
print(sum(dp[-1][N//2+1:]))

### FIXED CODE ###

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

dp = [[0.] * (N+1) for _ in range(N+1)]
dp[0][0] = 1.

for i in range(1, N+1):
    for j in range(i+1):
        prob = dp[i-1][j-1]*p[i-1]
        if i > 0:
            prob += dp[i-1][j]*(1.-p[i-1])
        dp[i][j] = max(dp[i][j], prob)
print(sum(dp[-1][N//2+1:]))
### BUGGY CODE ###

from itertools import permutations

n,m,r = map(int,input().split())
R = list(map(int,input().split()))

edges=[[10**9 for i in range(n+1)] for i in range(n+1)]

for i in range(m):
  a,b,c = map(int,input().split())
  edges[a][b] = c
  edges[b][a] = c


for k in range(1,n+1):
  for i in range(1,n+1):
    for j in range(i,n+1):
      edges[i][j] = min(edges[i][k]+edges[k][j], edges[i][j])
      edges[j][i] = edges[i][j]

# print(edges)

permutations
ans = 10**9
for i in permutations(R):
  tmp = 0
  for j in range(r-1):
    # print("i",i,"j",j)
    tmp += edges[i[j]][i[j+1]]
  ans = min(tmp, ans)

print(ans)

### FIXED CODE ###

from itertools import permutations

n,m,r = map(int,input().split())
R = list(map(int,input().split()))
inf = 10**9

edges=[[inf for i in range(n+1)] for i in range(n+1)]

for i in range(m):
  a,b,c = map(int,input().split())
  edges[a][b] = c
  edges[b][a] = c


for k in range(1,n+1):
  for i in range(1,n):
    for j in range(i,n+1):
      if edges[i][j] > edges[i][k] + edges[k][j]:
        edges[i][j] = edges[i][k]+edges[k][j]
        edges[j][i] = edges[i][j]


ans = inf
for i in permutations(R):
  tmp = 0
  for j in range(r-1):
    tmp += edges[i[j]][i[j+1]]
  ans = min(tmp, ans)

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

a, b, c, k = map(int, input().split())

s = []
x = 0

for i in range(a):
    s.append(1)

for i in range(b):
    s.append(0)

for i in range(c):
    s.append(-1)
    
for i in range(k):
    x += s[i]
    
print(x)


### FIXED CODE ###

a, b, c, k = map(int, input().split())

s = []
x = 0

if k <= a:
    print(k)
elif k <= a + b:
    print(a)
elif k <= a + b + c:
    print(2 * a + b - k)
else:
    print(a - c)
### BUGGY CODE ###

from collections import deque
 
x4 = [ 1,0,-1,0 ]
y4 = [ 0,1,0,-1 ] 
max_int = 2**63-1
 
 
h,w = map(int, input().split(' '))
S = []
for i in range(h):
    S.append(input())

grid = [[False]*(w+2) for _ in range(h+2)]
for i in range(h):
    for j in range(w):
        grid[i+1][j+1] = S[i][j] == '.'

ans = 0
 
for i in range(1,h+1):
    for j in range(1,w+1):
        if not grid[i][j]:
            continue
 
        visited = [[False for o in range(w+2)] for l in range(h+2)]
        q = deque()
        d = [[max_int for o in range(w+2)] for l in range(h+2)]
 
        visited[i][j] = True
        q.append((i,j))
        d[i][j] = 0
 
        while q:
            cy, cx = q.popleft()
            visited[cy][cx] = True
            for dy,dx in zip(y4,x4):
                ny = cy + dy
                nx = cx + dx
                if grid[ny][nx] and not visited[ny][nx]:
                    q.append((ny, nx))
                    d[ny][nx] = min(d[ny][nx], d[cy][cx] + 1)
                    ans = max(d[ny][nx], ans)
 
print(ans)

### FIXED CODE ###

from itertools import count, combinations, product

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

grid = [[False]*(W+2) for _ in range(H+2)]

for i in range(1,H+1):
    S = input()
    for j,v in zip(range(1,W+1),S):
        grid[i][j] = v == '.'

visited = [[0 if v else float('inf') for v in row] for row in grid]
cnt = 1
def dist(p1,p2):
    global cnt
    q = [p1]
    visited[p1[0]][p1[1]] = cnt 
    for d in count():
        if not q:
            break
        nq = []
        for x,y in q:
            if (x,y) == p2:
                cnt += 1
                return d
            else:
                for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
                    if visited[x+dx][y+dy] < cnt:
                        visited[x+dx][y+dy] = cnt
                        nq.append((x+dx,y+dy))
        q = nq
    cnt += 1
    return float('inf')

emp = [(i,j) for i,j in product(range(H+2),range(W+2)) if grid[i][j]]

print(max(dist(*p) for p in combinations(emp,2)))
### BUGGY CODE ###

from collections import defaultdict

def get_sum(num):
    return num*(num-1)/2


N = int(input())
S = []
D = defaultdict(int)
ans = 0
for i in range(N):
    s = str(sorted(input()))
    D[s] += 1

for k, v in D.items():
    ans += get_sum(v)


print(int(ans))



### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline

def get_sum(num):
    return num*(num-1)/2


N = int(input())
S = []
D = defaultdict(int)
ans = 0
for _ in range(N):
    s = str(sorted(input()))
    D[s] += 1

for k, v in D.items():
    ans += get_sum(v)


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

import sys
input = sys.stdin.readline

import numpy as np

n, k = map(int, input().split())
A = np.array(sorted(list(map(int, input().split()))))
F = np.array(sorted(list(map(int, input().split())), reverse=True))
def is_time(x):
  c = 0
  for i in range(n):
    c = np.maximum(A - x//F, 0).sum()
  if c <= k:
    return True
  return False
ng = -1
ok = max(A*F)
while ok - ng > 1:
  m = (ng + ok)//2
  if is_time(m):
    ok = m
  else:
    ng = m
print(ok)

### FIXED CODE ###

n, k = map(int, input().split())
A = sorted(list(map(int, input().split())))
F = sorted(list(map(int, input().split())))[::-1]
def is_time(x):
  c = 0
  for i in range(n):
    c += max(0, A[i] - x//F[i])
  if c <= k:
    return True
  return False
ng = -1
ok = 0
for i in range(n):
  ok = max(ok, A[i]*F[i])
while ok - ng > 1:
  m = (ng + ok)//2
  if is_time(m):
    ok = m
  else:
    ng = m
print(ok)
### BUGGY CODE ###

import numpy as np
n,k=list(map(int,input().split()))
a=sorted(list(map(int,input().split())))
f=sorted(list(map(int,input().split())),reverse=True)
b = [a[i]*f[i] for i in range(n)]

def judgement(x):
    judge = -1
    cnt = 0
    for i in range(n):
        if b[i]>x:
            cnt += -((x-b[i])//f[i])
        if cnt > k:
            judge = False
            break
    if cnt <= k:
        judge = True
    return judge

low=0
high=np.amax(b)
while low<high:
    mid = (low + high)//2
    if judgement(mid) == False:
        low=mid+1
    else:
        high=mid
print(low)

### FIXED CODE ###

n,k=list(map(int,input().split()))
a=sorted(list(map(int,input().split())))
f=sorted(list(map(int,input().split())),reverse=True)
b = [a[i]*f[i] for i in range(n)]

def judgement(x):
    judge = -1
    cnt = 0
    for i in range(n):
        if b[i]>x:
            cnt += -((x-b[i])//f[i])
        if cnt > k:
            judge = False
            break
    if cnt <= k:
        judge = True
    return judge

low=0
high=max(b)
while low<high:
    mid = (low + high)//2
    if judgement(mid) == False:
        low=mid+1
    else:
        high=mid
print(low)
### BUGGY CODE ###

def main():
        N,Q = map(int,input().split())
        ab = []
        for _ in range(N - 1):
        	ab.append(list(map(int,input().split())))
        px =[]
        for _ in range(Q):
        	px.append(list(map(int,input().split())))
        ab.sort()
        # px.sort()
        plus = []
        for _ in range(N):
        	plus.append(0)

        for p,x in px:
                plus[p - 1] += x 

        for a,b in ab:
                plus[b - 1] += plus[a - 1]
        for p in plus:
                print(p)

if __name__ == '__main__':
        main()


### FIXED CODE ###

def main():
        N,Q = map(int,input().split())
        ab = [list(map(int,input().split())) for _ in range(N - 1)]
        px = [list(map(int,input().split())) for _ in range(Q)]
        ab.sort()
        # px.sort()
        plus = [0 for _ in range(N)]

        for p,x in px:
                plus[p - 1] += x 

        for a,b in ab:
                plus[b - 1] += plus[a - 1]
        for p in plus:
                print(p)

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

def main():
    n,m=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in [0]*m]
    if n==1:
        for a,b in ab:
            print(min(a,b))
        return
    for a,b in ab:
        while a!=b:
            a,b=min(a,b),max(a,b)
            b=(b+n-2)//n
        print(a)
    
main()

### FIXED CODE ###

def main():
    n,m=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in [0]*m]
    if n==1:
        for a,b in ab:
            print(min(a,b))
        return
    for a,b in ab:
        while a!=b:
            a,b=min(a,b),max(a,b)
            b=(b+n-2)//n
        print(a)
    
main()
### BUGGY CODE ###

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

biggest = 0
humidai = 0

result = 0


for i in range(N-1):
    tmp=0
    for j in range(i+1,N):
        tmp += A[j]
    
    result += A[i]*tmp

    if result>10**9+7:
        result = result%(10**9+7)

result = result%(10**9+7)

print(result)

### FIXED CODE ###

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

biggest = 0
humidai = 0

result = 0

tmp_list = []

tmp=sum(A)

for i in range(N-1):

    # for j in range(i+1,N):
        # tmp += A[j]
    tmp -= A[i]
    
    result += A[i]*tmp

    if result>10**9+7:
        result = result%(10**9+7)

result = result%(10**9+7)

print(result)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(500000)

N = int(input())

tree = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    tree[a].append((b, c))
    tree[b].append((a, c))

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

from functools import lru_cache
@lru_cache(maxsize=None)
def dfs(start, end, dist, f=None):
    if start == end:
        return 0
    for n, d in tree[start]:
        if n == f:
            continue
        if n == end:
            return dist + d
        else:
            result = dfs(n, end, dist+d, start)
            if result is not None:
                return result

xy = [list(map(int, input().split())) for i in range(Q)]

for i in range(Q):
    x, y = xy[i]
    print(dfs(x, K, 0) + dfs(K, y, 0))


### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)

N = int(input())

tree = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    tree[a].append((b, c))
    tree[b].append((a, c))

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

def dfs(start, dist, dists, f=None):
    for n, d in tree[start]:
        if n == f:
            continue
        dists[n] = dist + d
        dfs(n, dist+d, dists, start)

xy = [list(map(int, input().split())) for i in range(Q)]

dists = [0] * (N+1)
dfs(K, 0, dists)

for i in range(Q):
    x, y = xy[i]
    print(dists[x] + dists[y])
### BUGGY CODE ###

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
mod = 10 ** 9 + 7
dp = [0] * (1 << n)
dp[0] = 1
for i in range(1, 1 << n):
    k = bin(i).count("1")
    for j in range(n):
        if i >> j & 1 and a[k - 1][j]:
            dp[i] += dp[i ^ (1 << j)]
    dp[i] %= mod
print(dp[(1 << n)-1])


### FIXED CODE ###

mod = 10**9+7
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
dp = [0]*(1 << n)
dp[0] = 1
for i in range(1, 1 << n):
    k = bin(i).count("1")
    for j in range(n):
        if i >> j & 1 and a[k-1][j]:
            dp[i] += dp[i ^ (1 << j)]
    dp[i] %= mod
print(dp[(1 << n)-1])
### BUGGY CODE ###

from operator import mul
from functools import reduce
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
MOD = 10 ** 9 + 7

ans = 0

def com(n, r):
  r = min(r, n - r)
  numer = reduce(mul, range(n, n - r, -1), 1)
  denom = reduce(mul, range(1, r + 1), 1)
  return numer // denom

for i in range(N):
  if N - 1 - i >= K - 1:
    ans += (A[- i - 1] - A[i]) * com(N - 1 - i, K - 1)
    ans = ans % MOD
    
    
print(ans % MOD)

### FIXED CODE ###

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

ans = 0

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

N2 = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N2 + 1):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)

#print(cmb(n, r, p))
for i in range(len(A)):
  if N - 1 - i >= K - 1:
    ans += (A[- i - 1] - A[i]) * cmb(N - 1 - i, K - 1, MOD)
    ans = ans % MOD
    
    
print(ans % MOD)
### BUGGY CODE ###

H, W, M = map(int, input().split())
h, w = [], []
h_dic, w_dic = {}, {}

for i in range(M):
    h_i, w_i = map(int, input().split())
    h.append(h_i)
    w.append(w_i)
    if h_i in h_dic:
        h_dic[h_i] += 1
    else:
        h_dic[h_i] = 1
    if w_i in w_dic:
        w_dic[w_i] += 1
    else:
        w_dic[w_i] = 1
        
max_h_items = [[0,0]]
max_w_items = [[0,0]]

for key, value in h_dic.items():
    if value > max_h_items[0][1]:
        max_h_items = [[key, value]]
    elif value == max_h_items[0][1]:
        max_h_items.append([key, value])
for key, value in w_dic.items():
    if value > max_w_items[0][1]:
        max_w_items = [[key, value]]
    elif value == max_w_items[0][1]:
        max_w_items.append([key, value])

max_count = 0
for mh in max_h_items:
    for mw in max_w_items:
        count = 0
        for i in range(M):
            if h[i] == mh[0] or w[i] == mw[0]:
                count += 1
        max_count = max(max_count, count)
print(max_count)

### FIXED CODE ###

H, W, M = map(int, input().split())
h_dic, w_dic = {}, {}
m = set()
for i in range(M):
    h_i, w_i = map(int, input().split())
    m.add((h_i, w_i))
    if h_i in h_dic:
        h_dic[h_i] += 1
    else:
        h_dic[h_i] = 1
    if w_i in w_dic:
        w_dic[w_i] += 1
    else:
        w_dic[w_i] = 1
        
max_h_items = [[0,0]]
max_w_items = [[0,0]]

for key, value in h_dic.items():
    if value > max_h_items[0][1]:
        max_h_items = [[key, value]]
    elif value == max_h_items[0][1]:
        max_h_items.append([key, value])
for key, value in w_dic.items():
    if value > max_w_items[0][1]:
        max_w_items = [[key, value]]
    elif value == max_w_items[0][1]:
        max_w_items.append([key, value])
s = max_h_items[0][1] + max_w_items[0][1] - 1
for mh in max_h_items:
    for mw in max_w_items:
        if (mh[0], mw[0]) not in m:
            s = mh[1]+mw[1]
            print(s)
            break
    if s == max_h_items[0][1] + max_w_items[0][1]:
        break
if s == max_h_items[0][1] + max_w_items[0][1] - 1:
    print(s)
### BUGGY CODE ###

N=int(input())
a=[int(i) for i in input().split()]
x,y,z=0,0,0
for i in a:
    if i==1:
        x+=1
    elif i==2:
        y+=1
    elif i==3:
        z+=1
n=x+y*2+z*3


dp=[[[-1 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0]=0
def calc(h,i,j):
    global n,N
    if h+i+j==0 or h<0 or h>n or i<0 or i>n or j<0:
        return 0
    if dp[h][i][j]!=-1:
        return dp[h][i][j]
    dp[h][i][j]=(calc(h-1,i,j)*h/N+calc(h+1,i-1,j)*i/N+calc(h,i+1,j-1)*j/N+1)*N/(h+i+j)
    return dp[h][i][j]

a=calc(x,y,z)
print(dp[x][y][z])


### FIXED CODE ###

import numpy as np
from numba import njit

N=int(input())
a=[int(i) for i in input().split()]
x,y,z=0,0,0
for i in a:
    if i==1:
        x+=1
    elif i==2:
        y+=1
    elif i==3:
        z+=1


dp=np.full((N+1,N+1,N+1),-1,dtype=np.float64)

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

@njit('f8(i8,i8,i8,i8,f8[:,:,:])', cache=True)
def calc(h,i,j,N,dp):
    if h+i+j==0:
        return 0
    if dp[h][i][j]>=0:
        return dp[h][i][j]
    A=1
    if h>=1:
        A+=calc(h-1,i,j,N,dp)*h/N
    if i>=1:
        A+=calc(h+1,i-1,j,N,dp)*i/N
    if j>=1:
        A+=calc(h,i+1,j-1,N,dp)*j/N
    A=A*N/(h+i+j)
    dp[h][i][j]=A
    return A

a=calc(x,y,z,N,dp)

print(dp[x][y][z])