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

N, M = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(M)]

from collections import defaultdict
from collections import deque
g = defaultdict(set)

for x, y in XY:
  g[x].add(y)

  
def bfs(u):
  s = deque([u])
  done = {u: 0}
  while s:
    u = s.popleft()
    for v in g[u]:
      done[v] = done[u] + 1
      s.append(v)
  return done
  
ans = 0
for i in range(1, N+1):
  d = bfs(i)
  ans = max(ans, max(d.values()))
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(M)]

from collections import defaultdict
from collections import deque
from collections import Counter
g = defaultdict(set)

for x, y in XY:
  g[x].add(y)
  
  
def TSort(g):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v))
    V = set(V)
    funin = Counter()
    
    for u in V:
        for v in g[u]:
            funin[v] += 1
    
    q = deque()
    for v in V:
        if funin[v] == 0:
            q.append(v)
    L = []
    while q:
        u = q.popleft()
        L.append(u)
        for v in g[u]:
            funin[v] -= 1
            if funin[v] == 0:
                q.append(v)
    return L

  
D = Counter()
ns = TSort(g)
for u in ns:
  for v in g[u]:
    D[v] = max(D[v], D[u] + 1)
print(D.most_common()[0][1])
### BUGGY CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

A = list(map(int, input()))
N = len(A)
mod = 2019

dp0 = [0] * mod
dp1 = [0] * mod
dp2 = [0] * mod
dp0[0] = 1
for i, a in enumerate(A):
    nxt0 = [0] * mod
    nxt1 = [0] * mod
    nxt2 = [0] * mod
    nxt0[0] = dp0[0]
    nxt1[a] = dp0[0]
    for j in range(mod):
        nxt = (j*10+a) % mod
        nxt1[nxt] += dp1[j]
        nxt2[nxt] += dp1[j]
        nxt2[j] += dp2[j]
    dp0 = nxt0
    dp1 = nxt1
    dp2 = nxt2
ans = dp2[0]
print(ans)


### FIXED CODE ###

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

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

S = input()
N = len(S)
mod = 2019

acc = [0] * (N+1)
mul = 1
for i in range(N-1, -1, -1):
    x = int(S[i]) * mul
    acc[i] = (acc[i+1] + x) % mod
    mul *= 10
    mul %= mod

C = Counter(acc)
ans = 0
for v in C.values():
    ans += v*(v-1) // 2
print(ans)
### BUGGY CODE ###

import sys
import numpy as np

def I():
	return int(sys.stdin.readline().rstrip())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def main():
	N = I()
	a = np.zeros((N,))
	b = np.zeros((N,))
	c = np.zeros((N,))
	for i in range(N):
		a[i], b[i], c[i] = LI()
	
	dp = np.zeros((N, 3), dtype=int)
	dp[0, 0] = a[0]
	dp[0, 1] = b[0]
	dp[0, 2] = c[0]
	for i in range(1, N):
		dp[i, 0] = max(dp[i-1, 1] + a[i], dp[i-1, 2] + a[i])
		dp[i, 1] = max(dp[i-1, 0] + b[i], dp[i-1, 2] + b[i])
		dp[i, 2] = max(dp[i-1, 0] + c[i], dp[i-1, 1] + c[i])
	print(np.max(dp[-1, :]))

if __name__ == "__main__":
	main()

### FIXED CODE ###

import sys
# import numpy as np

def I():
	return int(sys.stdin.readline().rstrip())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def main():
	N = I()
	activity = []
	for i in range(N):
		activity.append(LI())
	
	# dp = np.zeros((N, 3), dtype=int)
	dp = [[0, 0, 0] for _ in range(N)]
	dp[0][0] = activity[0][0]
	dp[0][1] = activity[0][1]
	dp[0][2] = activity[0][2]
	for i in range(1, N):
		dp[i][0] = max(dp[i-1][1] + activity[i][0], dp[i-1][2] + activity[i][0])
		dp[i][1] = max(dp[i-1][0] + activity[i][1], dp[i-1][2] + activity[i][1])
		dp[i][2] = max(dp[i-1][0] + activity[i][2], dp[i-1][1] + activity[i][2])
	print(max(dp[-1]))

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

from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

s = stdin.readline().rstrip()
k = int(stdin.readline().rstrip())

def main():
    finish = set()
    S = len(s)
    for i in range(S):
        for j in range(i+1,S+1):
            finish.add(s[i:j])

    finish = list(finish)
    finish.sort()
    print(finish[k-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

s = stdin.readline().rstrip()
k = int(stdin.readline().rstrip())


finish = set()
S = len(s)

for i in range(S):
    for j in range(1,6):
        finish.add(s[i:i+j])

finish = list(finish)
finish.sort()

print(finish[k-1])
### BUGGY CODE ###

import itertools
n = int(input())
s = tuple(map(int, input()))
a = tuple(set(itertools.combinations(s, 3)))
ans = len(a)
print(ans)


### FIXED CODE ###

n = int(input())
s = tuple(map(int, input()))
f = [
    [] for i in range(10)
]
ans = 0

for i in range(n-2):
    if len(f[s[i]]) != 0:
        continue
    else:
        for j in range(i+1, n-1):
            if s[j] in f[s[i]]:
                continue
            else:
                f[s[i]].append(s[j])
                a = tuple(set(s[j+1:]))
                ans += len(a)

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

s=str(0)+input()
t=str(0)+input()

dp=[[0]*(len(t)) for i in range(len(s))]

for i in range(1,len(s)):
    for j in range(1,len(t)):
        if s[i]==t[j]:
            dp[i][j]=dp[i-1][j-1]+1
        else:dp[i][j]=max(dp[i-1][j],dp[i][j-1])

ans_rev=""
i=len(s)-1
j=len(t)-1

while i>0 and j>0:
    if s[i]==t[j]:
        ans_rev+=s[i]
        i-=1
        j-=1
    elif dp[i][j]==dp[i-1][j]:i-=1
    elif dp[i][j]==dp[i][j-1]:j-=1

ans=ans_rev[::-1]
print(ans)


### FIXED CODE ###

s=str(0)+input()
t=str(0)+input()

dp=[[0]*(len(t)) for i in range(len(s))]

for i in range(1,len(s)):
    for j in range(1,len(t)):
        if s[i]==t[j]:
            dp[i][j]=dp[i-1][j-1]+1
        else:dp[i][j]=max(dp[i-1][j],dp[i][j-1])

ans=[""]*dp[i][j]
i=len(s)-1
j=len(t)-1
k=dp[i][j]-1
while i>0 and j>0:
    if s[i]==t[j]:
        ans[k]=s[i]
        k-=1
        i-=1
        j-=1
    elif dp[i][j]==dp[i-1][j]:i-=1
    elif dp[i][j]==dp[i][j-1]:j-=1

print("".join(ans))
### BUGGY CODE ###

from collections import Counter
n = int(input())
A = sorted(list(map(int,input().split())))
c = Counter(A)
lst = list(c.values())
l,r = 0, len(lst)-1
while sum(lst) > len(lst):
    if lst[l] <= 1:
        l += 1
        continue
    else:
        if lst[r] <= 1:
            r -= 1
            continue
        else:
            lst[l] -= 1
            lst[r] -= 1
print(sum(lst))

### FIXED CODE ###

from collections import Counter
n = int(input())
A = map(int,input().split())
k = len(Counter(A))
print(k if k%2!=0 else k-1)
### BUGGY CODE ###

N = int(input())
As = list(map(int,input().split()))
sums = 0
moder = 1000000007
for i in range(N-1):
  for j in range(N-i-1):
    sums+=(As[i]*As[i+j+1])
print(sums%moder)

### FIXED CODE ###

N = int(input())
As = list(map(int,input().split()))
sums = 0
moder = 1000000007
s=[0 for i in range(N-1)]
s[-1] = As[-1]
for i in range(N-2):
  s[-(i+2)] = s[-(i+1)]+As[-(i+2)]

for i in range(N-1):
  sums+= (As[i]*s[i])%moder
print(sums%moder)
### BUGGY CODE ###

n = int(input())
d = list(map(int, input().split()))


ans = 1
if d[0] == 0 and d.count(0) == 1:
	for i in range(1, max(d)):
		x = d.count(i)
		ans = ans * (x**(d.count(i+1)))
else:
	ans = 0

print(ans%998244353)

### FIXED CODE ###

n = int(input())
d = list(map(int, input().split()))

dd = sorted(d)
c = []
j = 0
for i in range(max(d)+1):
	tmp = 0
	while dd[j] == i:
		tmp += 1
		j += 1
		if j == n:
			break
	c.append(tmp)

ans = 1
if d[0] == 0 and d.count(0) == 1 and c.count(0) == 0:
	for i in range(1, max(d)):
		ans = ans * (c[i]**c[i+1])
else:
	ans = 0

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

#D
S=input()
s=[]
for i in range(len(S)):
    s.append(S[i])
q=int(input())
for i in range(q):
    t=input().split()
    if t[0]=='1':
        s.reverse()
    elif t[1]=='1':
        s.insert(0,t[2])
    else:
        s.append(t[2])
        
print(''.join(s))

### FIXED CODE ###

s=[input()]
q=int(input())
turn=True
l=""
for i in range(q):
    qq=input().split()
    if qq[0]=='1':
        turn=not turn
    else:
        if turn==bool(int(qq[1])-2):
            l+=qq[2]
        else:
            s.append(qq[2])

text=l[::-1]+"".join(s)
print(text if turn else text[::-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

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

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

f=[0]*N
for _ in range(Q):
    p,x=map(int,input().split())
    p-=1
    f[p]+=x

ans=[0 for _ in range(N)]
visited=[False]*N
def c(i,p):
    if visited[i]:
        return 
    visited[i]=True
    w=f[i]+p
    ans[i]=w
    ch=graph[i]
    for x in ch:
        c(x,w)

c(0,0)
print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N,Q,*abpx=map(int,sys.stdin.read().split())

graph=[[] for _ in range(N)]
for a,b in zip(*[iter(abpx[:2*(N-1)])]*2):
    a-=1
    b-=1
    graph[a].append(b)
    graph[b].append(a)

f=[0]*N
for p,x in zip(*[iter(abpx[2*(N-1):])]*2):
    p-=1
    f[p]+=x

ans=[0 for _ in range(N)]
visited=[False]*N
def c(i,p):
    if visited[i]:
        return 
    visited[i]=True
    w=f[i]+p
    ans[i]=w
    ch=graph[i]
    for x in ch:
        c(x,w)

c(0,0)
print(*ans)
### BUGGY CODE ###

def InputData():
    
    sequence_len = int(input())
    sequence = [None] + [int(a) for a in input().split(" ")]

    return sequence_len, sequence

def bubbleSort(A):
    cnt = 0
    for i in range(len(A)-1):
        for j in range(len(A)-1, i+1, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                cnt += 1
    
    return cnt

def PrintOut(cnt):
    print(cnt)

def main():
    [sequence_len, sequence] = InputData()
    cnt = bubbleSort(sequence)
    PrintOut(cnt)

if __name__=="__main__":
    main()


### FIXED CODE ###

def InputData():
    
    sequence_len = int(input())
    sequence = [int(a) for a in input().split(" ")]

    return sequence_len, sequence

def bubbleSort(A):
    cnt = 0
    for i in range(len(A)-1):
        for j in range(len(A)-1, i+1, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                cnt += 1
    
    return cnt

def merge(sequence, left, mid, right):
    global merge_cnt
    n1 = mid - left
    n2 = right - mid
    sequence_left = sequence[left:left + n1]
    sequence_right = sequence[mid:mid + n2]
    sequence_left.append(float('inf'))
    sequence_right.append(float('inf'))

    left_cnt = 0
    right_cnt = 0
    for i in range(left, right):
        if sequence_left[left_cnt] <= sequence_right[right_cnt]:
            # print(sequence_left[left_cnt])
            sequence[i] = sequence_left[left_cnt]
            left_cnt += 1
        else:
            # print(sequence_right[right_cnt])
            sequence[i] = sequence_right[right_cnt]
            right_cnt += 1
            merge_cnt += n1 - left_cnt

def mergeSort(sequence, left, right):
    if left + 1 < right:
        # print(merge_cnt)
        mid = (left + right) // 2
        mergeSort(sequence, left, mid)
        mergeSort(sequence, mid, right)
        merge(sequence, left, mid, right)

def PrintOut(cnt):
    print(cnt)

def main():
    [sequence_len, sequence] = InputData()
    # cnt = bubbleSort(sequence)
    global merge_cnt
    merge_cnt = 0
    mergeSort(sequence, 0, sequence_len)
    PrintOut(merge_cnt)

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

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

for _ in range(m):
    i = A.index(max(A))
    A[i] /= 2
A = [int(a) for a in A]

print(sum(A))


### FIXED CODE ###

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

A = [a * (-1) for a in A]
import heapq
heapq.heapify(A)

for _ in range(m):
    a = heapq.heappop(A) * (-1)
    heapq.heappush(A, a // 2 * (-1))

print(abs(sum(A)))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
l = []
for i in range(1,N+1):
    l.append(A.count(i))
    print(l[i-1])
    if sum(l)==N-1:
        break
num = N-len(l)
print(("0\n"*num).strip())

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
l = []
for _ in range(N):
    l.append(0)
for i in A:
    l[i-1] +=1
for x in l:
    print(x)
### BUGGY CODE ###

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
S = sr()
Q = ir()
K = lr()
for k in K:
    answer = 0
    dp = [0, 0, 0] # 'D', 'M', count of M
    for i in range(N):
        s = S[i]
        if i >= k:
            t = S[i-k]
            if t == 'D':
                dp[0] -= 1
                if dp[2] > 0:
                    dp[1] -= dp[2]
            elif t == 'M':
                dp[2] -= 1
        if s == 'D':
            dp[0] += 1
        elif s == 'M':
            dp[1] += dp[0]
            dp[2] += 1
        elif s == 'C':
            answer += dp[1]        
    print(answer)        
# 50

### FIXED CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
S = np.array(list('_' + sr()))
Q = ir()
K = lr()
isD = (S == 'D')
isM = (S == 'M')
isC = (S == 'C')
cumD = isD.cumsum()
cumM = isM.cumsum()

for k in K:
    x = cumD.copy()
    x[k:] -= cumD[:-k]
    x *= isM
    x[k+1:] -= isD[1:-k] * (cumM[k:-1] - cumM[:-k-1])
    answer = (x.cumsum() * isC).sum()
    print(answer)
# 05
### BUGGY CODE ###

import math
N = int(input())

t = 0
a = 0
for i in range(N):
    T, A = map(int, input().split())
    if i == 0:
        t += T
        a += A
        continue
    if (T >= t and A >= a):
        t = T
        a = A
        continue

    max_ta = max(t, a)
    g = math.gcd(t, a)
    tg, ag = t // g, a // g
    if (T, A) != (tg, ag):
        sum_t, sum_a = T * max_ta, A * max_ta
        # print(sum_t, sum_a)
        while True:
            sum_t -= T
            sum_a -= A
            if sum_t < t or sum_a < a:
                sum_t += T
                sum_a += A
                break
        t = sum_t
        a = sum_a
        continue

print(t + a)


### FIXED CODE ###

import math
N = int(input())

t = 0
a = 0
for i in range(N):
    T, A = map(int, input().split())
    if i == 0:
        t += T
        a += A
        continue
    if (T >= t and A >= a):
        t = T
        a = A
        continue

    max_ta = max(t, a)
    g = math.gcd(t, a)
    tg, ag = t // g, a // g
    if (T, A) != (tg, ag):
        sum_t, sum_a = T * max_ta, A * max_ta
        # print(sum_t, sum_a)

        cout_sn = min((sum_t - t) // T, (sum_a - a) // A)
        # while True:
        sum_t -= T * cout_sn
        sum_a -= A * cout_sn
        # if sum_t < t or sum_a < a:
        #     sum_t += T
        #     sum_a += A
        #     break
        t = sum_t
        a = sum_a
        continue

print(t + a)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def print_ans(N, S):
    """Test Case
    >>> print_ans(4, "0224")
    3
    >>> print_ans(6, "123123")
    17
    >>> print_ans(19, "3141592653589793238")
    329
    """
    s = set()
    for i in range(N):
        for k in range(i+1,N):
            for l in range(k+1, N):
                s.add(S[i] + S[k] + S[l])
    print(len(s))



    
if __name__ == '__main__':
    N = int(input().rstrip())
    S = input().rstrip()
    print_ans(N, S)


### FIXED CODE ###

import sys
input = sys.stdin.readline
lists = ['{0:03d}'.format(i) for i in range(1000)]
import re
def check(target, a):
    ans = re.search(a, target)
    if ans == None:
        return None
    else:
        return target[ans.start()+1:]

def print_ans(N, S):
    """Test Case
    >>> print_ans(4, "0224")
    3
    >>> print_ans(6, "123123")
    17
    >>> print_ans(19, "3141592653589793238")
    329
    """
    # s = set()
    # for i in range(N):
    #     for k in range(i+1,N):
    #         for l in range(k+1, N):
    #             s.add(S[i] + S[k] + S[l])
    # print(len(s))
    ans = 0
    for a in lists:
        tmp = S
        for i in range(3):
            tmp = check(tmp, a[i])
            if tmp == None:
                break
        if tmp != None:
            ans += 1
    print(ans)


    # print(check('123','4'))


    
if __name__ == '__main__':
    N = int(input().rstrip())
    S = input().rstrip()
    print_ans(N, S)
### BUGGY CODE ###

mod = 10**9+7 #出力の制限
N = 5001
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

import sys

sys.setrecursionlimit(10**4)
input=sys.stdin.buffer.readline

N=int(input())
edge=[[] for i in range(N)]
for i in range(N-1):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)


dp=[[] for i in range(N)]
sz=[0 for i in range(N)]
def dfs(v,pv):
    sz[v]=1
    dp[v]=[0]*(sz[v]+1)
    dp[v][1]=1
    for nv in edge[v]:
        if nv!=pv:
            dfs(nv,v)
            merged=[0]*(sz[v]+sz[nv]+1)
            for i in range(sz[v]+1):
                for j in range(sz[nv]+1):
                    merged[i+j]=(merged[i+j]+dp[v][i]*dp[nv][j])%mod
            sz[v]+=sz[nv]
            dp[v] =merged
    for k in range(1,sz[v]+1):
        dp[v][0]=(dp[v][0]-(g1[k]*g2[k//2])%mod*((k+1)%2)*dp[v][k])%mod

dfs(0,-1)

print((-dp[0][0]*pow(inverse[2],N//2,mod))%mod)


### FIXED CODE ###

mod = 10**9+7 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

import sys

sys.setrecursionlimit(10**4)

N=int(input())
edge=[[] for i in range(N)]
parent=[0]*N
deg=[1]*N
deg[0]=0
for i in range(N-1):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)


def prv(v,pv):
    for nv in edge[v]:
        if nv!=pv:
            parent[nv]=v
            prv(nv,v)

prv(0,-1)

for i in range(N):
    new=[]
    for v in edge[i]:
        if v!=parent[i]:
            new.append(v)
    edge[i]=new


from collections import deque
ans = list(v for v in range(N) if deg[v]==0)
deq = deque(ans)
used = [0]*N

while deq:
    v = deq.popleft()
    for t in edge[v]:
        deg[t] -= 1
        if deg[t]==0:
            deq.append(t)
            ans.append(t)


dp=[[] for i in range(N)]
sz=[0 for i in range(N)]

for v in ans[::-1]:
    sz[v]=1
    dp[v]=[0]*(sz[v]+1)
    dp[v][1]=1
    for nv in edge[v]:
        merged=[0]*(sz[v]+sz[nv]+1)
        for i in range(sz[v]+1):
            for j in range(sz[nv]+1):
                merged[i+j]=(merged[i+j]+dp[v][i]*dp[nv][j])%mod
        sz[v]+=sz[nv]
        dp[v] =merged
    for k in range(1,sz[v]+1):
        dp[v][0]=(dp[v][0]-(g1[k]*g2[k//2])%mod*((k+1)%2)*dp[v][k])%mod

print((-dp[0][0]*pow(inverse[2],N//2,mod))%mod)
### BUGGY CODE ###

from fractions import Fraction

MOD = 10 ** 9 + 7

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

csum = [0]
t = 0
for i in range(1, n + 1):
    t += Fraction(1, i)
    csum.append(t)

fact = 1
t = 1
while t <= n:
    fact *= t
    fact %= MOD
    t += 1

# jが何回加算されるか
ans = 0
for j in range(n):
    coef = 0
    coef += csum[abs(j - 0) + 1]  # 左側加算
    coef += csum[abs(j - (n - 1)) + 1]  # 右側加算
    coef -= 1  # 自身を減算
    # print(coef, a[j])
    ans += coef * a[j]
    ans %= MOD

ans *= fact
ans %= MOD

print(ans)

### FIXED CODE ###

MOD = 10 ** 9 + 7

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

csum_invs = [0]
t = 0
for i in range(1, n + 1):
    t += pow(i, MOD - 2, MOD)
    t %= MOD
    csum_invs.append(t)
# print(csum_invs)

fact = []
t = 1
for i in range(1, n + 1):
    t *= i
    t %= MOD
    fact.append(t)
# print(fact)

ans = 0
for i in range(n):
    # print(i)
    t = a[i] * (csum_invs[n - i] + csum_invs[i + 1] - 1)
    t %= MOD
    ans += t

ans *= fact[-1]
ans %= MOD

print(ans)

'''
逆元の求め方: フェルマーの小定理
    a ** (-1) ≡ a ** (p - 2) (mod p)
    b / a ≡ b * a **(p - 2)
    だから、/ a をしたければ、* a ** (p -2) をすればよい
'''
### BUGGY CODE ###

N = int(input())
s=0
for i in range(1,N+1):
    s += i-1
print(s)

### FIXED CODE ###

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

N = int(input())
word = []
ans = 0
temp = 0
for i in range (0,N):
    temp = 0
    inp = sorted(input())
    for j in range (0,len(word)):
        for k in range (0,10):
            if word[j][k] != inp[k]:
                temp = 0
                break
            temp = 1
        if temp == 1: 
            ans = ans + word[j][10]
            word [j][10] = word[j][10] + 1
            temp = 1
            break
    if temp == 0:
        inp.append(1)
        word.append(inp)
print(ans)



### FIXED CODE ###

n = int(input())
d = {}
ans = 0


for i in range (0,n):
    temp = 0
    linp =  sorted(input())
    inp = ''.join(linp)
    if inp in d:
        ans = ans + d[inp]
        d[inp] = d[inp] + 1
    else:
        d[inp] = 1
print(ans)
### BUGGY CODE ###

K, S=list(map(int, input().split()))
c=0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z==S:
                c+=1
print(c)

### FIXED CODE ###

K, S=list(map(int, input().split()))
c=0
for i in range(0, min(2*K+1, S+1)):
    for j in range(0, min(K+1,i+1)):
        if j<=K and i-j<=K and S-i<=K:
            c+=1
print(c)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

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

es = [[] for _ in range(N)]
g = [0] * N
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    es[a].append(b)
    g[a] += 1
    es[b].append(a)
    g[b] += 1

s = -1
b = -1
for i, gg in enumerate(g):
    if gg > b:
        b = gg
        s = i

gs = [0] * (N + 1)
gs[s] = -1
gs[N] = -1
visited = [False] * N
ans = 1


def rec(v, bf):
    global ans
    if visited[v]:
        return
    visited[v] = True
    gs[v] += 1
    gs[bf] += 1
    ans *= K - gs[bf]
    ans %= mod

    for nv in es[v]:
        if not visited[nv]:
            rec(nv, v)
    return


rec(s, N)
print(ans)

# print(gs)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

input = sys.stdin.readline


def rec(v, bf):
    global ans
    gs[v] += 1
    gs[bf] += 1
    ans = ans * (K - gs[bf]) % mod
    for nv in es[v]:
        if nv == bf: continue
        rec(nv, v)
    return


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

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

gs = [0] * (N + 1)
gs[0] = -1
gs[N] = -1

ans = 1

rec(0, N)
print(ans)