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

MOD = 998244353


def main():
    from bisect import bisect_left
    N, K = (int(i) for i in input().split())
    S = set()
    for _ in range(K):
        le, ri = (int(i) for i in input().split())
        for i in range(le, ri+1):
            S.add(i)

    A = sorted(S)
    memo = [0] * (N+1)
    memo[0] = 1

    def dfs(N):
        if N < 0:
            return 0
        if memo[N] != 0:
            return memo[N]
        ret = 0
        idx = bisect_left(A, N)
        for i in A[idx::-1]:
            ret += dfs(N - i)
            ret %= MOD
        memo[N] = ret
        return ret

    print(dfs(N-1))
    # print(memo, A)


if __name__ == '__main__':
    main()


### FIXED CODE ###

MOD = 998244353


def main():
    N, K = (int(i) for i in input().split())
    LR = [[int(i) for i in input().split()] for j in range(K)]

    dp = [0] * (N+2)
    dp[1] = 1
    dp[2] = -1
    for i in range(1, N+1):
        for le, ri in LR:
            if i+le <= N:
                dp[i+le] += dp[i]
                dp[i+le] %= MOD
            if i+ri+1 <= N:
                dp[i+ri+1] -= dp[i]
                dp[i+ri+1] %= MOD
        dp[i+1] += dp[i]
        dp[i+1] %= MOD
    print(dp[N])


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

S = input()
l = len(S)
A,B,C,q = [0]*l,[0]*l,[0]*l,[0]*l
inf = 1000000007
for i in range(l):
    if S[i] == 'A':
        A[i] = 1
    elif S[i] == 'B':
        B[i] = 1
    elif S[i] == 'C':
        C[i] = 1
    else:
        q[i] = 1

for i in range(l-1):
    A[i+1] += A[i]
    B[i+1] += B[i]
    C[i+1] += C[i]
    q[i+1] += q[i]

ans = 0
for i in range(1,l-1):
    if S[i] == 'B':
        ans += (A[i-1]) * (C[-1]-C[i]) * (3**q[-1])
        ans %= inf
        if q[-1] >= 1:
            ans += (q[i-1]) * (C[-1] - C[i]) * (3**(q[-1]-1))
            ans %= inf
            ans += (A[i-1]) * (q[-1] - q[i]) * (3**(q[-1]-1))
            ans %= inf
        if q[-1] >= 2:
            ans += (q[i-1]) * (q[-1] - q[i]) * (3**(q[-1]-2))
            ans %= inf

    elif S[i] == '?':
        ans += (A[i-1]) * (C[-1]-C[i]) * (3**(q[-1]-1))
        ans %= inf
        if q[-1] >= 2:
            ans += (q[i-1]) * (C[-1] - C[i]) * (3**(q[-1]-2))
            ans %= inf
            ans += (A[i-1]) * (q[-1] - q[i]) * (3**(q[-1]-2))
            ans %= inf
        if q[-1] >= 3:
            ans += (q[i-1]) * (q[-1] - q[i]) * (3**(q[-1]-3))
            ans %= inf

print(ans%inf)


 

### FIXED CODE ###

S = input()
l = len(S)
A,B,C,q = [0]*l,[0]*l,[0]*l,[0]*l
inf = 1000000007
for i in range(l):
    if S[i] == 'A':
        A[i] = 1
    elif S[i] == 'B':
        B[i] = 1
    elif S[i] == 'C':
        C[i] = 1
    else:
        q[i] = 1

for i in range(l-1):
    A[i+1] += A[i]
    B[i+1] += B[i]
    C[i+1] += C[i]
    q[i+1] += q[i]

ans = 0
for i in range(1,l-1):
    if S[i] == 'B':
        ans += (A[i-1]) * (C[-1]-C[i]) * pow(3,q[-1],inf)
        ans %= inf
        if q[-1] >= 1:
            ans += (q[i-1]) * (C[-1] - C[i]) * pow(3,q[-1]-1,inf)
            ans %= inf
            ans += (A[i-1]) * (q[-1] - q[i]) * pow(3,q[-1]-1,inf)
            ans %= inf
        if q[-1] >= 2:
            ans += (q[i-1]) * (q[-1] - q[i]) * pow(3,q[-1]-2,inf)
            ans %= inf

    elif S[i] == '?':
        ans += (A[i-1]) * (C[-1]-C[i]) * pow(3,q[-1]-1,inf)
        ans %= inf
        if q[-1] >= 2:
            ans += (q[i-1]) * (C[-1] - C[i]) * pow(3,q[-1]-2,inf)
            ans %= inf
            ans += (A[i-1]) * (q[-1] - q[i]) * pow(3,q[-1]-2,inf)
            ans %= inf
        if q[-1] >= 3:
            ans += (q[i-1]) * (q[-1] - q[i]) * pow(3,q[-1]-3,inf)
            ans %= inf

print(ans%inf)
### BUGGY CODE ###

s = input()
t = input()
def lcs(s,t):
    m = len(s)
    n = len(t)
    dp = [[""]*(n+1) for _ in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            x = s[i-1]
            y = t[j-1]
            if x == y:
                dp[i][j] = dp[i-1][j-1]+x
            else:
                dp[i][j] = dp[i-1][j]
                if len(dp[i][j]) < len(dp[i][j-1]):
                    dp[i][j] = dp[i][j-1]
    return dp[i][j]
print(lcs(s,t))

### FIXED CODE ###

s = input()
t = input()
m = len(s)
n = len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        x = s[i-1]
        y = t[j-1]
        if x == y:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = dp[i-1][j]
            if dp[i][j] < dp[i][j-1]:
                dp[i][j] = dp[i][j-1]
res = ""
while n != 0 and m != 0:
    if dp[m][n] == dp[m-1][n]:
        m -= 1
    elif dp[m][n] == dp[m][n-1]:
        n -= 1
    else:
        n -= 1
        m -= 1
        res = s[m] + res
print(res)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import heapq

N,M = (int(x) for x in input().split())
A = list(map(int, input().split()))
heapq.heapify(A)
for i in range(M):
    B,C = (int(x) for x in input().split())
    for j in range(B):
        temp = heapq.heappop(A)
        if temp < C:
            heapq.heappush(A,C)
        else:
            heapq.heappush(A,temp)
            break
print(sum(A))

### FIXED CODE ###

import sys
input = sys.stdin.readline
import heapq

N,M = (int(x) for x in input().split())
A = list(map(int, input().split()))
BC = []
changeable = N
broke = False
for i in range(M):
    B,C = (int(x) for x in input().split())
    BC.append((C*(-1),B))
heapq.heapify(A)
heapq.heapify(BC)
for i in range(M):
    t1 = heapq.heappop(BC)
    if t1[1] < changeable:
        for j in range(t1[1]):
            t2 = heapq.heappop(A)
            if t2 < t1[0] * (-1):
                heapq.heappush(A,t1[0]*(-1))
            else:
                heapq.heappush(A,t2)
                broke = True
                break
        else:
            changeable -= t1[1]
    else:
        for j in range(changeable):
            t2 = heapq.heappop(A)
            if t2 < t1[0] * (-1):
                heapq.heappush(A,t1[0]*(-1))
            else:
                heapq.heappush(A,t2)
                break
        break
    if broke:
        break
print(sum(A))
### BUGGY CODE ###

import unittest
import functools


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think([2, 3, 4]), 13)

    def test_2(self):
        self.assertEqual(think([12, 12, 12, 12, 12]), 5)

    def test_3(self):
        self.assertEqual(think([1000000, 999999, 999998]), 996989508)

    def test_4(self):
        self.assertEqual(gcd(3, 2), 1)


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7

    lcm_of_all_a = functools.reduce(lambda x, y: lcm(x, y), a, 1)
    # lcm_of_all_a %= mode   # THIS LINE IS KEY POINT

    b = map(lambda x: lcm_of_all_a * inverse(x, mode) % mode, a)
    return sum(b) % mode


def write(result):
    print(result)


def lcm(a, b):
    return (a * b) // gcd(a, b)


def gcd(a, b):
    if a < b:
        return gcd(b, a)

    while True:
        if a % b == 0:
            return b
        a, b = b, a % b


def inverse(x, mode):
    return pow(x, mode - 2, mode)


if __name__ == '__main__':
    # unittest.main()
    solve()

### FIXED CODE ###

import unittest
import functools


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think([2, 3, 4]), 13)

    def test_2(self):
        self.assertEqual(think([12, 12, 12, 12, 12]), 5)

    def test_3(self):
        self.assertEqual(think([1000000, 999999, 999998]), 996989508)

    def test_4(self):
        self.assertEqual(gcd(3, 2), 1)


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7

    lcm_of_all_a = 1
    for e in a:
        lcm_of_all_a = lcm(lcm_of_all_a, e)

    lcm_of_all_a %= mode
    result = 0
    for e in a:
        result += lcm_of_all_a * inverse(e, mode) % mode
        result %= mode
    return result


def write(result):
    print(result)


def lcm(a, b):
    return a // gcd(a, b) * b 


def gcd(a, b):
    if a < b:
        return gcd(b, a)

    while True:
        if a % b == 0:
            return b
        a, b = b, a % b


def inverse(x, mode):
    return pow(x, mode - 2, mode)


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

from functools import reduce

def gcd(x, y):
    if x < y:
        x, y = y, x
    while x % y != 0:
        r = x % y
        x = y
        y = r
    return y

def inv(x):
    return pow(x, MOD-2, MOD)

def lcm(a, b):
    return a * b // gcd(a, b)

def addmod(a, b):
    return (a+b) % MOD
  
  
N = int(input())
a_list = list(map(int, input().split()))
MOD = 10 ** 9 + 7

l = reduce(lcm, a_list)
ans = reduce(addmod, (l//a for a in a_list))

print(ans%MOD)

### FIXED CODE ###

from functools import reduce

def gcd(x, y):
    if x < y:
        x, y = y, x
    while x % y != 0:
        r = x % y
        x = y
        y = r
    return y

def inv(x):
    return pow(x, MOD-2, MOD)

def lcm(a, b):
    return a * b // gcd(a, b)

def lcm_list(l:list):
    return reduce(lcm, l, 1)
  
N = int(input())
a_list = list(map(int, input().split()))
MOD = 10 ** 9 + 7

num = lcm_list(a_list) % MOD
ans = 0
for a in a_list:
    ans += (num * pow(a, MOD-2, MOD)) % MOD

print(ans%MOD)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().rstrip().split(" ")))
b = []
for i in a:
    b.append(i)
    b.reverse()
s = [str(k) for k in b]
print(" ".join(s))


### FIXED CODE ###

n = int(input())
a = list(map(int,input().rstrip().split(" ")))
b1 = []
b2 = []
ans = []
if n % 2 == 0:
    for i in range(n):
        if i % 2 == 0:
            b1.append(a[i])
        else:
            b2.append(a[i])
    b2.reverse()
    ans = b2 + b1
    print(" ".join(str(i) for i in ans))
else:
    for i in range(n):
        if i % 2 == 0:
            b1.append(a[i])
        else:
            b2.append(a[i])
    b1.reverse()
    ans = b1 + b2
    print(" ".join(str(i) for i in ans))
### BUGGY CODE ###

def readInt():
    return list(map(int, input().split()))

n = int(input())
a = readInt()

# print(n)
# print(a)
l = []
ans = 0
for i in a:
    i %= 10**9+7 
# print(a)

for i in range(n-1):
    for j in range(i+1,n):
        b = (a[i] * a[j]) % (10**9+7)
        l.append(b)
# print(l)

ans = sum(l) % (10**9+7)

print(ans)


### FIXED CODE ###

def readInt():
    return list(map(int, input().split()))

n = int(input())
a = readInt()

# print(n)
# print(a)
b = 0
ans = 0
for i in a:
    i %= 10**9+7 
# print(a)

for i in range(n-1):
    b += a[i]
    ans += a[i+1] * b

ans %= (10**9+7)

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

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, *A = map(int, read().split())
    A.sort()

    B = [True] * N
    for i in range(N):
        if not B[i]:
            continue
        if i < N - 1 and A[i + 1] == A[i]:
            B[i] = False
        for j in range(i + 1, N):
            if A[j] % A[i] == 0:
                B[j] = False

    print(B.count(True))
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, *A = map(int, read().split())
    A.sort()

    M = 10 ** 6
    B = [True] * (M + 1)
    B[0] = False
    ans = 0
    for i in range(N):
        if not B[A[i]]:
            continue
        if i < N - 1 and A[i + 1] == A[i]:
            B[A[i]] = False
        else:
            ans += 1
        for n in range(2 * A[i], M + 1, A[i]):
            B[n] = False

    print(ans)
    return


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

import sys
input = sys.stdin.readline
n,k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
p = tuple(p)

chk = 0
for i in range(n-k+1):
  m = sum(p[i:k+i])
  chk = max(chk,m)
  if chk == m:
    a = p[i:k+i]

ans = 0
for j in a:
  ans += (j+1)/2
print(ans)

### FIXED CODE ###

def main():  
  import sys
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines
  import numpy as np #pypy不可
  n,k = map(int,readline().split())
  p =  np.array(read().split(),np.int32)
  np.cumsum(p,out=p)
  chk = p[k-1]
  for i in range(n-k):
    c = p[i+k]-p[i]
    chk = max(c,chk)
  print((chk+k)/2)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def lcs():
    x = raw_input()
    y = raw_input() 
    x = " " + x
    y = " " + y
    c = [[0 for i in xrange(len(x))] for j in xrange(len(y))]
    for i in xrange (1,len(y)):
        for j in xrange (1,len(x)):
            if x[j] == y[i]:
                c[i][j] = c[i-1][j-1] + 1
            elif c[i-1][j] >= c[i][j-1]:
                c[i][j] = c[i-1][j]
            else:
                c[i][j] = c[i][j-1]
    return max(max(c))
n = input() 
for i in xrange (n): 

    print lcs()

### FIXED CODE ###

def lcs():
    x, y = raw_input(), raw_input()
    b1 = [0 for k in range(len(y)+1)]
    for i in xrange(len(x)):
        a = x[i]
        b2 = b1 + []
        for j in xrange(len(y)):
            if a == y[j]:
                b1[j+1] = b2[j] + 1
            elif b1[j+1] < b1[j]:
                b1[j+1] = b1[j]
    print max(b1)
 
n = input()
for i in xrange(n):
    lcs()
### BUGGY CODE ###


a,b,c,k = list(map(int,input().split()))
a_1 = 1
c_1 = -1

ans = 0

while k > 0:
    if a > 0:
        ans += a_1
        a -= 1
    elif b > 0:
        b -= 1
    else:
        ans += c_1
    k -= 1
print(ans)


### FIXED CODE ###

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

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

import math 

s = int(input())
s_1 = math.sqrt(s)
s_1 = int(s_1)
a = []
for i in range(1, s_1+1):
    if s%i==0:
        a.append(i)
ans = [0,0,a[-1],0,a[-1],s//a[-1]]
print(*ans)

### FIXED CODE ###

import math 
MOD = int(1e9)

s = int(input())
if s==1000000000000000000:
    ans = [0,0,MOD,0,0,MOD]
    print(*ans)
    exit()

ans = [0,0,MOD,1]
x,y = 0,0
y = s//MOD + 1
x = MOD - s%MOD
ans.append(x)
ans.append(y)
print(*ans)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
LR = [list(map(int, input().split())) for _ in range(q)]

for i in range(q):
    l, r = LR[i][0], LR[i][1]
    tmp = s[l-1:r]
    print(tmp.count(("AC")))


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
LR = [list(map(int, input().split())) for _ in range(q)]

t = [0]*(n+1)

for i in range(n):
    t[i+1] = t[i] + (1 if s[i:i+2]=="AC" else 0)

for i in LR:
    l, r = i[0], i[1]
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

N=int(input())
lis = list(map(int, input().split()))
j = 'YES'
for Nx in range(N):
  for Ax in range(1, N-Nx):
    if lis[Nx] == lis[Nx+Ax]:
      j = 'NO'
      break
    else:
      continue
    break
print(j)

### FIXED CODE ###

N=int(input())
lis = list(map(int, input().split()))
j = 'YES'
if len(lis) != len(set(lis)):
  j = 'NO'
print(j)
### BUGGY CODE ###

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

ans = -1*float('inf')

for i in range(N):
    k = i
    Cc = []
    Ct = 0
    while 1:
        k = P[k]-1
        Cc.append(C[k])
        if i == k:
            break
    l = len(Cc)
    Ct = sum(Cc)
    t = 0
    for j in range(l):
        t += Cc[j]
        if j >= K:break
        now = t
        if Ct > 0:
            e = (K-j-1)//l
            now +=  Ct*e
        ans = max(ans,now)
print(ans)

### FIXED CODE ###

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

ans = -1*float('inf')

for i in range(N):
    k = i
    Cc = []
    Ct = 0
    while 1:
        k = P[k]-1
        Cc.append(C[k])
        if i == k:
            break
    l = len(Cc)
    Ct = sum(Cc)
    t = 0
    for j in range(l):
        t += Cc[j]
        if j >= K:break
        now = t
        if Ct > 0:
            e = (K-j-1)//l
            now +=  Ct*e
        ans = max(ans,now)
print(ans)
### BUGGY CODE ###

l=list(input())
count=0
while True:
    flag=True
    for i in range(len(l)-1):
        if l[i]!=l[i+1]:
            del l[i:i+2]
            flag=False
            count+=2
        if i>=len(l)-2:
            break
    if flag:
        break
print(count)


### FIXED CODE ###

l=list(input())
o=0
z=0
for i in range(len(l)):
    if l[i]=="0":
        z+=1
    elif l[i]=="1":
        o+=1

if z > o:
    print(2*o)
else:
    print(2*z)
### BUGGY CODE ###

L, R = map(int, input().split())

ans = 10 ** 9
for i in range(L, R):
  for j in range(i+1, R+1):
    tmp = (i*j)%2019
    if ans > tmp:
      ans = tmp
    if ans == 0:
      break
print(ans)

### FIXED CODE ###

L, R = map(int, input().split())

ans = 10 ** 9
for i in range(L, R):
    for j in range(i+1, R+1):
        tmp = (i*j)%2019
        if ans > tmp:
            ans = tmp
        if ans == 0:
            break
    else:
        continue
    break
print(ans)
### BUGGY CODE ###

N, K  = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(K)]
L.sort()
S = set()
for l in L:
  S = S|set([i for i in range(l[0], l[1]+1)])
DP = [0]*N
DP[0]=1
for i in range(1, N):
  for j in S:
    if i>=j:
      DP[i] += DP[i-j]
      DP[i] %= 998244353
    else:
      break
  continue
print(DP[-1])

### FIXED CODE ###

N, K = map(int, input().split())
L = []
for _ in range(K):
  a, b = map(int, input().split())
  L.append((a,b))
L.sort()
DP_1 = [0]*N
DP_2 = [0]*(N+1)
DP_1[0], DP_2[1] = 1, 1
mod = 998244353
for i in range(1, N):
  for l in L:
    if l[0]>i:
      break
    elif l[1]>i:
      DP_1[i] += DP_2[i-l[0]+1]
      DP_1[i] %= mod
    elif l[1]<=i:
      DP_1[i] += DP_2[i-l[0]+1]-DP_2[i-l[1]]
      DP_1[i] %= mod
  DP_2[i+1] = DP_2[i] + DP_1[i]
  DP_2[i+1] %= mod
print(DP_1[-1]%mod)
### BUGGY CODE ###

import collections
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
n=int(input())
a=list(map(int,input().split()))
id=0
frac=[1]*(10**5+10)
p=10**9+7
c=collections.Counter(a)
id=c.most_common()[0][0]
buf=[]
for i in range(1,10**5+10):
    frac[i]=(frac[i-1]*i)%p
#print(frac[:6])
for i in range(n+1):
    if a[i]==id:
        buf.append(i)
#print(a,l,buf)
N=n+1
short=N-(max(buf)-min(buf))

#print(short,N)

for i in range(1,n+2,1):
    if short-i<0:
        sub1=0
    else:
        sub1 = (((frac[short] * modinv(frac[i], p)) % p) * modinv(frac[short - i], p)) % p

    if short-i-1<0:
        sub2=0
    else:
        sub2 = (((frac[short - 1] * modinv(frac[i], p)) % p) * modinv(frac[short - i - 1], p)) % p
    all=(((frac[N]*modinv(frac[i],p))%p)*modinv(frac[N-i],p))%p

    #print(all,sub1,sub2)
    print(((all-sub1)%p+sub2)%p)

### FIXED CODE ###

import collections
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
n=int(input())
a=list(map(int,input().split()))
id=0
frac=[1]*(10**5+10)
fracinv=[0]*(10**5+10)
p=10**9+7
c=collections.Counter(a)
id=c.most_common()[0][0]
buf=[]
for i in range(1,10**5+10):
    frac[i]=(frac[i-1]*i)%p
for i in range(0,10**5+10):
    fracinv[i]=modinv(frac[i],p)
#print(frac[:6])
for i in range(n+1):
    if a[i]==id:
        buf.append(i)
#print(a,l,buf)
N=n+1
short=N-(max(buf)-min(buf))

#print(short,N)

for i in range(1,n+2,1):
    if short-i<0:
        sub1=0
    else:
        sub1 = (((frac[short] * fracinv[i]) % p) * fracinv[short-i]) % p

    if short-i-1<0:
        sub2=0
    else:
        sub2 = (((frac[short - 1] * fracinv[i]) % p) * fracinv[short - i - 1]) % p
    all=(((frac[N]*fracinv[i])%p)*fracinv[N-i])%p

    #print(all,sub1,sub2)
    print((all-(sub1-sub2)%p)%p)
### BUGGY CODE ###

def myAnswer(N:int) ->int:
   ans = 1
   for i in range(1,N+1):
      ans *=i
   return ans % (10**9 + 7)

def modelAnswer():
   tmp=1
def main():
   N = int(input())
   print(myAnswer(N))


if __name__ == '__main__':
   main()


### FIXED CODE ###

from math import factorial
def myAnswer(N:int) ->int:
   ans =factorial(N)
   return ans % (10**9 + 7)

def modelAnswer():
   tmp=1
def main():
   N = int(input())
   print(myAnswer(N))


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

N=int(input())
A=[int(input()) for _ in range(N)]
B=sorted(A)[:N-1]
for i in range(N):
    if  A[i]==max(A):
        print(max(B))
    else:
        print(max(A))

### FIXED CODE ###

N=int(input())
A=[int(input()) for _ in range(N)]
B=sorted(A)[:N-1]
m=max(A)
n=A.index(max(A))
for i in range(N):
    if  i!=n:
        print(m)
    else:
        print(max(B))
### BUGGY CODE ###

import sys

n = int(input())
blocks = []
for line in sys.stdin.readlines():
    w, s, v = map(int, line.split())
    blocks.append((w + s, w, s, v))
blocks.sort()

dp = [-1] * 20001
dp[0] = 0
for _, w, s, v in blocks:
    for i in range(min(s, 20000 - w), -1, -1):
        dp[i + w] = max(dp[i + w], dp[i] + v)
print(max(dp))


### FIXED CODE ###

import sys

n = int(input())
blocks = []
for line in sys.stdin.readlines():
    w, s, v = map(int, line.split())
    blocks.append((w + s, w, s, v))
blocks.sort()

dp = [-1] * 20001
dp[0] = 0
for _, w, s, v in blocks:
    for i in range(min(s, 20000 - w), -1, -1):
        dp[i + w] = max(dp[i + w], dp[i] + v)
print(max(dp))
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
maze = [list(input()) for i in range(H)]
dp = [[float('inf')]*W for i in range(H)]
dp[0][0] = 0

q = deque([[0, 0]])

while len(q):
    pos = q.popleft()
    posX, posY = pos
    if posX + 1 < W:
        rightX, rightY = posX + 1, posY
        if maze[posY][posX] == "." and maze[rightY][rightX] == "#":
            dp[rightY][rightX] = min(dp[posY][posX] + 1, dp[rightY][rightX])
        else:
            dp[rightY][rightX] = min(dp[posY][posX], dp[rightY][rightX])
        q.append([rightX, rightY])
        
    if posY + 1 < H:
        downX, downY = posX, posY + 1
        if maze[posY][posX] == "." and maze[downY][downX] == "#":
            dp[downY][downX] = min(dp[posY][posX] + 1, dp[downY][downX])
        else:
            dp[downY][downX] = min(dp[posY][posX], dp[downY][downX])
        q.append([downX, downY])

if maze[0][0] == "#":
    print(dp[-1][-1] + 1)
else:
    print(dp[-1][-1])

### FIXED CODE ###

H, W = map(int, input().split())
maze = [list(input()) for i in range(H)]
dp = [[float('inf')]*W for i in range(H)]
dp[0][0] = 0

for y in range(H):
    for x in range(W):
        if y == 0 and x == 0:
            continue
        
        if x >= 1:
            if maze[y][x - 1] == "." and maze[y][x] == "#":
                dp[y][x] = min(dp[y][x - 1] + 1, dp[y][x])
            else:
                dp[y][x] = min(dp[y][x - 1], dp[y][x])
        
        if y >= 1:
            if maze[y - 1][x] == "." and maze[y][x] == "#":
                dp[y][x] = min(dp[y - 1][x] + 1, dp[y][x])
            else:
                dp[y][x] = min(dp[y - 1][x], dp[y][x])

if maze[0][0] == "#":
    print(dp[-1][-1] + 1)
else:
    print(dp[-1][-1])
### BUGGY CODE ###

import itertools

N=int(input())
L=list(itertools.permutations(map(int,input().split())))
ANS=-1
for l in L:
  TMP = l[0]
  for i in range(1, N):
    TMP = (l[i] + TMP) / 2.0
  if ANS <= TMP:
    ANS = TMP
print(ANS)

### FIXED CODE ###

N=int(input())
L=list(map(int,input().split()))
L.sort()
ANS = L[0]
for i in range(1, N):
  ANS = (L[i] + ANS) / 2.0
  
print(ANS)