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

# E

# 入力
# input
N = int(input())
a_list = [0]*(N+1)
for i in range(N+1):
    a_list[N-i] = int(input())


# 10^5までの素数を計算
# list primes <= 10^5 
primes = list(range(10**5))
primes[0] = 0
primes[1] = 0
for p in range(2, 10**5):
    if primes[p]:
        for i in range(2*p, 10**5, p):
            primes[i] = 0
primes = [p for p in primes if p>0]
# primes <= N
p_list_small = [p for p in primes if p <= N]


# A_Nを素因数分解、Nより大きい素因数をp_list_largeに追加
# A_N, ..., A_0の最大公約数の素因数でやっても同じ
# list prime factors of A_N, if greater then N, add to p_list_large
# you can use prime factors of gcd(A_N, ..., A_0) instead 

p_list_large = []
A = abs(a_list[-1])
for p in primes:
    if A % p == 0:
        if p > N:
            p_list_large.append(p)
        while A % p == 0:
            A = A // p
if A != 1:
    p_list_large.append(A)

# 個別に条件確認
# check all p in p_list_small
# x^p ~ x (mod p)
res_list = []
for p in p_list_small:
    r = 0
    check_list = [0]*(N+1)
    for i in range(p):
        check_list[i] = a_list[i]
    for i in range(p, N+1):
        check_list[(i-1) % (p-1) + 1] += a_list[i]
    for i in range(p):
        if check_list[i] % p != 0:
            r = 1
    if r == 0:
        res_list.append(p)
        
# 個別に条件確認
# check all p in p_list_large
# a_i % p == 0
for p in p_list_large:
    r = 0
    for i in range(N+1):
        if a_list[i] % p != 0:
            r = 1
    if r == 0:
        res_list.append(p)
        
for p in res_list:
    print(p)

### FIXED CODE ###

# E

# 入力
# input
N = int(input())
a_list = [0]*(N+1)
for i in range(N+1):
    a_list[N-i] = int(input())


# 10^5までの素数を計算
# list primes <= 10^5 
primes = list(range(10**5))
primes[0] = 0
primes[1] = 0
for p in range(2, 10**5):
    if primes[p]:
        for i in range(2*p, 10**5, p):
            primes[i] = 0
primes = [p for p in primes if p>0]
# primes <= N
p_list_small = [p for p in primes if p <= N]


# A_Nを素因数分解、Nより大きい素因数をp_list_largeに追加
# A_N, ..., A_0の最大公約数の素因数でやっても同じ
# list prime factors of A_N, if greater then N, add to p_list_large
# you can use prime factors of gcd(A_N, ..., A_0) instead 

p_list_large = []
A = abs(a_list[-1])
for p in primes:
    if A % p == 0:
        if p > N:
            p_list_large.append(p)
        while A % p == 0:
            A = A // p
if A != 1:
    p_list_large.append(A)

# 個別に条件確認
# check all p in p_list_small
# x^p ~ x (mod p)
res_list = []
for p in p_list_small:
    r = 0
    check_list = [0]*(N+1)
    for i in range(p):
        check_list[i] = a_list[i]
    for i in range(p, N+1):
        check_list[(i-1) % (p-1) + 1] += a_list[i]
    for i in range(p):
        if check_list[i] % p != 0:
            r = 1
    if r == 0:
        res_list.append(p)
        
# 個別に条件確認
# check all p in p_list_large
# a_i % p == 0
for p in p_list_large:
    r = 0
    for i in range(N+1):
        if a_list[i] % p != 0:
            r = 1
    if r == 0:
        res_list.append(p)
        
for p in res_list:
    print(p)
### BUGGY CODE ###

N,Q = map(int, input().split())
S = str(input())

before = ''
i = 0
num = 0
data_list = {}
for s in S:
    if before == 'A' and s == 'C':
        num += 1
    before = s
    data_list[i] = num
    i += 1

ans = ''
for q in range(Q):
    r,l = map(int, input().split())
    ans += str(data_list[l-1]-data_list[r-1])+'\n'

print(ans.rstrip())

### FIXED CODE ###

N,Q = map(int, input().split())
S = str(input())

before = ''
i = 0
num = 0
data_list = {}
for s in S:
    if before == 'A' and s == 'C':
        num += 1
    before = s
    data_list[i] = num
    i += 1

ans = ''
for q in range(Q):
    r,l = map(int, input().split())
    ans += str(data_list[l-1]-data_list[r-1])+'\n'

print(ans.rstrip())
### BUGGY CODE ###

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

product = 1

for i in range(N):
    product *= A[i]

if product > 1000000000000000000:
    print(-1)
else:
    print(product)


### FIXED CODE ###

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

product = 1
flag = 0

if 0 in A:
    print(0)
else:
    for i in range(N):
        product *= A[i]
        if product > 1000000000000000000:
            flag += 1
            break
    if flag == 0:
        print(product)
    else:
        print(-1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
H = list(map(int, input().split()))
cnt = 0
ans = 0
Hd = sorted(H, reverse=True)


for i in range(N - 1):
    if ans > N - i:
        break

    else:
        idx = H.index(Hd[i])
        cnt = 0
        for j in range(idx, N - 1):
            if H[j] >= H[j + 1]:
                cnt += 1
            else:
                break
    if ans < cnt:
        ans = cnt

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
H = list(map(int, input().split()))
ans = []
cnt = 0
for i in range(N - 1):
    if H[i] >= H[i + 1]:
        cnt += 1
    else:
        ans.append(cnt)
        cnt = 0

ans.append(cnt)
print(max(ans))
### BUGGY CODE ###

def func(s,x):
    last=[0]*26
    score=0
    for i,v in enumerate(x,1):
        last[v]=i
        c=0
        for j in range(26):
            c+=s[j]*(i-last[j])
        score=score+s[i*26+v]-c
    return score
def main():
    d,*s=map(int,open(0).read().split())
    x=[t-1for t in s[26*-~d:d*27+26]]
    for d,q in zip(*[iter(s[27*-~d:])]*2):
        x[d-1]=q-1
        print(func(s,x))
main()

### FIXED CODE ###

from numba import njit
from numpy import int64
@njit('i8(i8[:],i8[:])',cache=True)
def func(s,x):
    last=[0]*26
    score=0
    for i,v in enumerate(x,1):
        last[v]=i
        c=0
        for j in range(26):
            c+=s[j]*(i-last[j])
        score=score+s[i*26+v]-c
    return score
def main():
    d,*s=map(int,open(0).read().split())
    s=int64(s)
    x=s[26*-~d:d*27+26]-1
    for d,q in s[27*-~d:].reshape(-1,2):
        x[d-1]=q-1
        print(func(s,x))
main()
### BUGGY CODE ###

N = int(input())
S = input()

min_turn = N + 1
for i in range(N + 1):
    min_turn = min(S[:i].count("W") + S[i:].count("E"), min_turn)

print(min_turn)


### FIXED CODE ###

N = int(input())
S = input()

# import random
# N = 3 * 10 ** 5
# S = "".join(["WE"[random.randint(0, 1)] for _ in range(N)])

to_east = 0
to_west = S[1:].count("E")

min_turn = to_east + to_west
for i in range(1, N):
    if min_turn == 0:
        break
    if S[i - 1] == "W":
        to_east += 1
    if S[i] == "E":
        to_west -= 1
    min_turn = min(to_east + to_west, min_turn)

print(min_turn)
### BUGGY CODE ###

s = input()
q = int(input())
string = []
for i in range(q):
    emir = input()
    if emir[0] == '1':
        s = s[::-1]
    if emir[0] == '2':
        if emir[2] == '1':
            s = emir[4] + s
        elif emir[2] == '2':
            s += emir[4]
print(s)

### FIXED CODE ###

s = input()
q = int(input())
string = []
is_normal = 1
saq = ""
sol = ""
for i in range(q):
    emir = input()
    if emir[0] == '1':
        is_normal *= -1
    elif emir[0] == '2':
        if is_normal == 1:
            if emir[2] == '1':
                sol += emir[4]
            elif emir[2] == '2':
                saq += emir[4]
        else:
            if emir[2] == '1':
                saq += emir[4]
            elif emir[2] == '2':
                sol += emir[4]
s = sol[::-1] + s + saq
if is_normal == -1:
    s = s[::-1]

print(s)
### BUGGY CODE ###

n,m = map(int,input().split())
a_lst = [int(input()) for i in range(m)]
dp = [0]*(n+1)
dp[0] = 1
x = 10**9 + 7

for i in range(1,n+1):
    if i in a_lst:
        continue
    else:
        if i==1:
            dp[i] = dp[i-1]
        elif i>1:
            dp[i] = (dp[i-2] + dp[i-1]) % x

answer = dp[-1]

print(answer)

### FIXED CODE ###

n,m = map(int,input().split())
a_lst = set(int(input()) for i in range(m))
dp = [0]*(n+1)
dp[0] = 1
x = 10**9 + 7

for i in range(1,n+1):
    if i in a_lst:
        continue
    else:
        if i==1:
            dp[i] = dp[i-1]
        elif i>1:
            dp[i] = (dp[i-2] + dp[i-1]) % x

answer = dp[-1]

print(answer)
### BUGGY CODE ###

import re

N, Q = [int(item) for item in re.split(r"\s", input())]
s = input()
t = []
d = []
for _ in range(Q):
    t_in, d_in = [item for item in re.split(r"\s", input())]
    t.append(t_in)
    d.append(d_in)


def check(i):
    """どっちに落ちるかを返す
    -1,0,1

    Args:
        i ([type]): [description]
    """

    if i < 0:
        return -1
    if i > N-1:
        return 1

    for q in range(Q):
        if t[q] == s[i]:
            if d[q] == "L":
                i -= 1
            if d[q] == "R":
                i += 1

            if i < 0:
                return -1
            if i > N-1:
                return 1
    return 0


s_index = -1  # include
e_index = N  # include
while s_index+1 < e_index:
    c_index = (s_index+e_index)//2
    if check(c_index) == -1:
        s_index = c_index
    else:
        e_index = c_index
left = s_index

s_index = -1  # include
e_index = N  # include
while s_index+1 < e_index:
    c_index = (s_index+e_index)//2
    if check(c_index) == 1:
        e_index = c_index
    else:
        s_index = c_index
right = e_index


print(right-left-1)


### FIXED CODE ###

N, Q = map(int, input().split())
s = input()
TD = [input().split() for i in range(Q)]


def simulate(n):
    if n == -1:
        return -1
    if n == N:
        return 1
    for t, d in TD:
        if t == s[n]:
            if d == "L":
                n -= 1
            else:
                n += 1
        if n == -1:
            return -1
        elif n == N:
            return 1
    return 0


l = -1
r = N
while l+1 < r:
    n = (l+r)//2
    sim = simulate(n)
    if sim == -1:
        l = n
    else:
        r = n
L = l

l = -1
r = N
while l+1 < r:
    n = (l+r)//2
    sim = simulate(n)
    if sim == 1:
        r = n
    else:
        l = n
R = r
print(R-L-1)
### BUGGY CODE ###

class ColorMgmt:
    def __init__(self, n):
        self.colors_hash = [set() for _ in range(n)]
        self.next_colors = [1] * n
    
    def set_color(self, v, c):
        self.colors_hash[v].add(c)
        if self.next_colors[v] != c:
            return
        cnt = 1
        while cnt in self.colors_hash[v]:
            cnt += 1
        self.next_colors[v] = cnt
    
    def get_color(self, v):
        return self.next_colors[v]


N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for _ in range(N)]
edge_cnt = [0] * N
for idx, (a, b) in enumerate(ab):
    a, b = a-1, b-1
    edge[a].append([b, a, 0, idx])
    edge_cnt[a] += 1
    edge_cnt[b] += 1
K = max(edge_cnt)

next_list = []
now_list = [0]
color_mgmt = ColorMgmt(N)
while len(now_list) > 0:
    for v in now_list:
        for idx, nextv in enumerate(edge[v]):
            if v == nextv[0]:
                continue
            colors1 = color_mgmt.get_color(nextv[1])
            colors2 = color_mgmt.get_color(nextv[0])
            color = max(colors1, colors2)
            color_mgmt.set_color(nextv[1], color)
            color_mgmt.set_color(nextv[0], color)
            edge[v][idx][2] = color
            next_list.append(nextv[0])
    
    now_list = list(next_list)
    next_list = []

ret = []
for edges in edge:
    for e in edges:
        ret.append(e)
ret.sort(key=lambda x:x[3])
print(K)
for r in ret:
    print(r[2])


### FIXED CODE ###

class ColorMgmt:
    from heapq import heappop, heappush
    def __init__(self, n):
        self.colors_hash = [set() for _ in range(n)]
        self.next_colors = [1] * n
    
    def set_color(self, v, c):
        self.colors_hash[v].add(c)
        while self.next_colors[v] in self.colors_hash[v]:
            self.next_colors[v] += 1
    
    def get_color(self, v):
        return self.next_colors[v]


N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for _ in range(N)]
edge_cnt = [0] * N
for idx, (a, b) in enumerate(ab):
    a, b = a-1, b-1
    edge[a].append([b, a, 0, idx])
    edge_cnt[a] += 1
    edge_cnt[b] += 1
K = max(edge_cnt)

next_list = []
now_list = [0]
color_mgmt = ColorMgmt(N)
while len(now_list) > 0:
    for v in now_list:
        for idx, nextv in enumerate(edge[v]):
            if v == nextv[0]:
                continue
            colors1 = color_mgmt.get_color(nextv[1])
            colors2 = color_mgmt.get_color(nextv[0])
            color = max(colors1, colors2)
            color_mgmt.set_color(nextv[1], color)
            color_mgmt.set_color(nextv[0], color)
            edge[v][idx][2] = color
            next_list.append(nextv[0])
    
    now_list = list(next_list)
    next_list = []

ret = []
for edges in edge:
    for e in edges:
        ret.append(e)
ret.sort(key=lambda x:x[3])
print(K)
for r in ret:
    print(r[2])
### BUGGY CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

s = input()

@lru_cache(None)
def F(s, k):
    # sの左からk文字目以降を整数と見なしたとき、
    # 2019で割った余りを返す
    if k == len(s)-1:
        return int(s[k])
    ret = F(s, k+1) + int(s[k])*pow(10, len(s)-1-k)
    ret %= 2019
    return ret

a = [0]*2020
for i in range(len(s)-1, -1, -1):
    a[F(s, i)] += 1

ans = a[0]
for i in range(2020):
    ans += a[i] * (a[i]-1) // 2

print(ans)

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

s = input()

@lru_cache(None)
def F(s, k):
    # sの左からk文字目以降を整数と見なしたとき、
    # 2019で割った余りを返す
    if k == len(s)-1:
        return int(s[k])
    ret = F(s, k+1) + int(s[k])*pow(10, len(s)-1-k, 2019)
    ret %= 2019
    return ret

a = [0]*2020
for i in range(len(s)):
    a[F(s, i)] += 1

ans = a[0]
for i in range(2020):
    ans += a[i] * (a[i]-1) // 2

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

import heapq
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += (self.rank[x] == self.rank[y])

def kruskal(n, edge):
    ans = 0
    uf = UnionFind(n)
    for i in range(len(edge)):
        d, v, u = heapq.heappop(edge)
        
        if uf.find(v) != uf.find(u):
            uf.union(v, u)
            ans += d
    return ans

n = int(input())
x, y = [None]*n, [None]*n
dist = [[0] * n for _ in range(n)]

for i in range(n):
    a, b = map(int, input().split())
    x[i] = (a, i)
    y[i] = (b, i)

x.sort(key=lambda x:x[0])
y.sort(key=lambda y:y[0])

edge = []
for i in range(n-1):
    heapq.heappush(edge, (x[i+1][0]-x[i][0], x[i][1], x[i+1][1]))
    heapq.heappush(edge, (y[i+1][0]-y[i][0], y[i][1], y[i+1][1]))

del x, y
print(kruskal(n, edge))

### FIXED CODE ###

import heapq
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += (self.rank[x] == self.rank[y])

def kruskal(n, edge):
    ans = 0
    uf = UnionFind(n)
    while True:
        d, v, u = heapq.heappop(edge)
        
        if uf.find(v) != uf.find(u):
            uf.union(v, u)
            n -= 1
            ans += d
        if n < 2: return ans
    return ans

n = int(input())
x, y = [None]*n, [None]*n

for i in range(n):
    a, b = map(int, input().split())
    x[i] = (a, i)
    y[i] = (b, i)

x.sort(key=lambda x:x[0])
y.sort(key=lambda y:y[0])

edge = []
for i in range(n-1):
    heapq.heappush(edge, (x[i+1][0]-x[i][0], x[i][1], x[i+1][1]))
    heapq.heappush(edge, (y[i+1][0]-y[i][0], y[i][1], y[i+1][1]))

del x, y
print(kruskal(n, edge))
### BUGGY CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N = int(input())
    MAX = int(N ** 0.5)

    def f(x, y, z, n):
        return x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x == n

    res = [0] * 10008

    for n in range(1, N + 1):
        ans = 0
        li = []
        for x in range(1, MAX + 1):
            for y in range(1, MAX + 1):
                delta = (y + x) ** 2 - 4 * (x ** 2 + y ** 2 + x * y - n)
                if delta >= 0:
                    z = (-(y + x) + (delta) ** 0.5) / 2
                    if z > 0 and z % 1 == 0 and f(x, y, z, n):
                        ans += 1
                        li.append((x, y, z))

        # print(n, ans, li)
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N = int(input())
    MAX = int(N ** 0.5)

    res = [0] * 10008

    ans = 0
    li = []
    for x in range(1, MAX + 1):
        for y in range(1, MAX + 1):
            for z in range(1, MAX + 1):
                tmp = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
                if tmp <= 10000:
                    res[tmp] += 1

    for i in range(1, N + 1):
        print(res[i])


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

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

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

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

A = [a for a in A if a != 0]
b = []

while A:
    M = max(A)
    for i in range(len(A)):
        if len(bin(M))==len(bin(A[i])):
            A[i] ^= M
    A = [a for a in A if a != 0]
    b.append(M)    

b = b[::-1]
ans_ = 0
for i in range(len(b)):
    M = b[i]
    for j in range(i+1,len(b)):
        m = b[j]
        if len(bin(M))==len(bin(M&m)):
            b[j] ^= M
    ans_ ^= M

ans += ans_*2
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
for a in A:
    ans ^= a
M = 2**60-1
b = M^ans
for i in range(N):
    A[i] &= b
A.sort(reverse=True)
for i in range(min(60,N)):
    a = A[i]
    if a == 0:
        break
    l = len(bin(a))-3
    for j in range(N):
        if j==i:
            continue
        if A[j]//2**l%2==1:
            A[j] ^= a
        else:
            if i < j:
                break
    A.sort(reverse=True)
s = 0
for a in A:
    s ^= a
ans += 2*s
print(ans)
### BUGGY CODE ###

while True:
    try:
        n = int(raw_input())
        count = 0
        for a in range(1000,-1,-1):
             if 0 <= n - a <= 3000:
                for b in range(1000,-1,-1):
                    if n - a - b > 2000:
                        break
                    elif 0 <= n - a - b <= 1000:
                        count += n-a-b+1
                    elif 1001 < n - a - b <= 2000:
                        count += (2000 - (n-a-b) + 1)
        print count
    except:
        break

### FIXED CODE ###

import sys
def N(n):
    return (n+1)*(n+2)*(n+3)/6
for n in sys.stdin:
    n = int(n)
    if n > 2000:
        n = 4000 - n
    if n < 1001:
        print N(n)
    else:
        m = n - 1000
        print N(n) - (N(2*m) - m - 1)/2
### BUGGY CODE ###

s=input()
n=len("s")
q=int(input())
l=[]
start=""
end=""
m=0
for i in range(q):
    l.append(input())
    if l[i]=="1":
        m += 1

    else:
        due,f,c=l[i].split()
        if (f=="1" and m % 2==0) or (f !="1" and m % 2==1) :
            start += c
        else:
            end += c
start=start[::-1]
s = start + s + end

if m % 2 ==1:

    s=s[::-1]

print(s)


### FIXED CODE ###

s=input()
n=len("s")
q=int(input())
l=[]
start=""
end=""
m=0
for i in range(q):
    l.append(input())
    if l[i]=="1":
        m += 1

    else:
        due,f,c=l[i].split()
        if (f=="1" and m % 2==0) or (f !="1" and m % 2==1) :
            start += c
        else:
            end += c
if m % 2 ==0:

    start=start[::-1]
    s = start + s + end

else:
    s = s + end
    s = s[::-1]
    s = s + start

print(s)
### BUGGY CODE ###

from collections import Counter

n = int(input())
cnt = Counter(input().split())
c1, c2, c3 = cnt['1'], cnt['2'], cnt['3']
total = c1 + 2 * c2 + 3 * c3
dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]

for k in range(1, n + 1):
    still = n / k
    for a1 in range(k, -1, -1):
        for a2 in range(min(k - a1, (total - a1) // 2), -1, -1):
            a3 = k - a1 - a2
            if a1 + 2 * a2 + 3 * a3 > total:
                break
            tmp = 0
            if a1:
                tmp += dp[a1 - 1][a2][a3] * a1
            if a2:
                tmp += dp[a1 + 1][a2 - 1][a3] * a2
            if a3:
                tmp += dp[a1][a2 + 1][a3 - 1] * a3
            dp[a1][a2][a3] = tmp / k + still
print(dp[c1][c2][c3])


### FIXED CODE ###

from collections import Counter

n = int(input())
cnt = Counter(input().split())
c1, c2, c3 = cnt['1'], cnt['2'], cnt['3']
total = c1 + 2 * c2 + 3 * c3
c23 = c2 + c3
dp = [[[0.0] * (c3 + 1) for _ in range(c2 + c3 + 1)] for _ in range(n + 2)]

for k in range(1, n + 1):
    still = n / k
    for a1 in range(k, max(-1, 2 * k - total - 1, k - c23 - 1), -1):
        dpap, dpac, dpan = dp[a1 - 1], dp[a1], dp[a1 + 1]
        for a2 in range(min(k - a1, c2 + c3), max(-1, 3 * k - 2 * a1 - total - 1, k - a1 - c3 - 1), -1):
            a3 = k - a1 - a2
            tmp = 0
            if a1:
                tmp += dpap[a2][a3] * a1
            if a2:
                tmp += dpan[a2 - 1][a3] * a2
            if a3:
                tmp += dpac[a2 + 1][a3 - 1] * a3
            dpac[a2][a3] = tmp / k + still
print(dp[c1][c2][c3])
### BUGGY CODE ###

N, Y = map(int, input().split())
ax = ay = az = -1
if 10000*N == Y:
	ay = az = 0
	print(str(N)+" "+str(ay)+" "+str(az))
else:	
	for x in range(N+1):
		for y in range(N+1):
			for z in range(N+1):
				total = 10000*x + 5000*y + 1000*z
				if total == Y and x+y+z == N:
					ax = x
					ay = y
					az = z
					break
	print(str(ax)+" "+str(ay)+" "+str(az))

### FIXED CODE ###

N, Y = map(int, input().split())
ax = ay = az = -1
for x in range(N+1):
	for y in range(N+1):
		if (N-x-y) < 0:
			continue
		total = 10000*x + 5000*y + 1000*(N-x-y)
		if total == Y:
			ax = x
			ay = y
			az = N-x-y
			break
	else:
		continue
	break
print(str(ax)+" "+str(ay)+" "+str(az))
### BUGGY CODE ###

N, A, B = map(int,input().split())
min = 0
max = 0
for i in range(0, N - 1):
    min += A
    max += B
if (max + A) - (min + B) + 1 < 0:
    print("0")
else:
    print((max + A) - (min + B) + 1)

### FIXED CODE ###

N, A, B = map(int,input().split())
min = A * (N - 1) + B
max = B * (N - 1) + A
if (max - min) + 1 < 0:
    print("0")
else:
    print((max - min) + 1)