Harryxun/stf_run huggingface dataset:
def gcd(*A):
    if len(A) == 1:
        return A[0]
    elif len(A) == 2:
        a, b = A
        tmp = a % b
        while tmp != 0:
            a, b = b, tmp
            tmp = a % b
        return b
    elif len(A) > 2:
        return gcd(gcd(*A[:2]), *A[2:])

N = int(input())
A = list(map(int, input().split()))
print(max(gcd(*(A[j] for j in range(N) if i != j)) for i in range(N)))

### FIXED CODE ###

def gcd(a, b):
    tmp = a % b
    while tmp != 0:
        a, b = b, tmp
        tmp = a % b
    return b

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

L = [0 for _ in range(N)]
R = [0 for _ in range(N)]

L[0], R[N - 1] = A[0], A[N - 1]

for i in range(N-1): # i=0,1,...N-2
    L[i + 1] = gcd(L[i], A[i + 1])
    R[N - i - 2] = gcd(R[N - i - 1], A[N - i - 2])

print(max(L[N-2], R[1], *(gcd(L[i], R[i+2]) for i in range(N-2))))
def popcount(n):
    ret=0
    while n!=0:
        if n%2==1:
            ret+=1
        n//=2
    return ret

def f(n):
    ret=0
    while True:
        n=n%popcount(n)
        if n!=0:
            ret+=1
        else:
            ret+=1
            break
    return ret

N=int(input())
X=input()
bit=[""]*N
for i in range(N):
    bit[i]=X[i]

n=int(X,2)
for i in range(N):
    tmp=n
    if bit[i]=="0":
        tmp+=2**(N-i-1)
    else:
        tmp-=2**(N-i-1)
    print(f(tmp))

### FIXED CODE ###

def popcount_int(n):
    return bin(n).count('1')

def popcount_bin(s):
    return s.count('1')

def poptimes(n,cnt=1):
    if n==0:
        return cnt
    else:
        n%=popcount_int(n)
        cnt+=1
        return poptimes(n,cnt)

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

S_int=int(S,2)
pc=popcount_bin(S)
pc_plus=S_int%(pc+1)
if pc!=1:
    pc_minus=S_int%(pc-1)

for i in range(N):
    if S[i]=='1':
        if pc!=1:
            tmp=pc_minus-pow(2,N-i-1,pc-1)
            print(poptimes(tmp%(pc-1)))
        else:
            print(0)
            continue
    else:
        tmp=pc_plus+pow(2,N-i-1,pc+1)
        print(poptimes(tmp%(pc+1)))
m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    A = [0 for j in range(len(str2)+1)]
    for char1 in str1:
        A_copy = A[:]
        for char2 in str2:
            if(char1==char2):
                A[k+1] = A_copy[k]+1
            elif(A[k] > A[k+1]):
                A[k+1] = A[k]
    print(A[-1])


### FIXED CODE ###

def LCS(str1,str2):
    A = [0 for _ in range(len(str2)+1)]
    for i in range(len(str1)):
        A_copy = A[:]
        for j in range(len(str2)):
            if(str1[i]==str2[j]):
                A[j+1] = A_copy[j]+1
            elif(A[j] > A[j+1]):
                A[j+1] = A[j]
    print(A[-1])


m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    LCS(str1,str2)
import collections
n = int(input())
a = list(map(int, input().split()))
dif = [0] * n
sum_c = 0
c = collections.Counter(a)
for i, v in c.items():
    if v < 2:
        continue
    val = v * (v - 1) // 2
    dif[i] = 2 * (v - 1) // 2
    sum_c += val
print('\n'.join([int(sum_c - data[i]) for i in a])


### FIXED CODE ###

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
dif = [0] * (n + 1)
sum_c = 0
c = Counter(a)
for i, v in c.items():
    if v < 2:
        continue
    val = v * (v - 1) / 2
    dif[i] = v - 1
    sum_c += val
print('\n'.join([str(int(sum_c - dif[i])) for i in a]))
from collections import Counter

U = 10**5
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD
    
def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
n = int(input())
A = list(map(int, input().split()))
x = Counter(A).most_common()[0][0]
left = A.index(x)
right = A[::-1].index(x)
print(n)
for k in range(2, n+2):
  ans = comb(n+1, k) - comb(left+right, k-1)
  ans %= MOD
  print(ans)

### FIXED CODE ###

from collections import Counter

U = 10**5+1
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD
    
def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
n = int(input())
A = list(map(int, input().split()))
x = Counter(A).most_common()[0][0]
left = A.index(x)
right = A[::-1].index(x)
print(n)
for k in range(2, n+2):
  ans = comb(n+1, k) - comb(left+right, k-1)
  ans %= MOD
  print(ans)
N, M = map( int, input().split())
A = list( map( int, input().split()))
Needs = [0,2,5,5,4,5,6,3,7,6]
A.sort(reverse = True)
V = [0]*N
Check = []
for a in A:
    if V[Needs[a]] == 0:
        Check.append(Needs[a])
        V[Needs[a]] = a
Check.sort()
dp = [-100]*(N+1)
dp[0] = 0

for x in Check:
    dp[x] = 1
for i in range(1,N):
    t = dp[i]
    if t == -100:
        continue
    for x in Check:
        if x + i <= N:
            if dp[x+i] < t + 1:
                dp[x+i] = t+1
ans = ""
t = N
W = [0]*10
while t > 0:
    for x in Check:
        if dp[t-x]+1 == dp[t]:
            W[V[x]] += 1
            t -= x
            break
for i in range(9,0,-1):
    ans += str(i)*W[i]
print(ans)


### FIXED CODE ###

N, M = map( int, input().split())
A = list( map( int, input().split()))
Needs = [0,2,5,5,4,5,6,3,7,6]
A.sort(reverse = True)
V = [0]*10
Check = []
for a in A:
    if V[Needs[a]] == 0:
        Check.append(Needs[a])
        V[Needs[a]] = a
Check.sort()
dp = [-100000]*(N+1)
dp[0] = 0

for x in Check:
    if x <= N:
        dp[x] = 1
for i in range(1,N):
    t = dp[i]
    for x in Check:
        if x + i <= N:
            if dp[x+i] < t + 1:
                dp[x+i] = t+1
ans = ""
t = N
W = [0]*10
while t > 0:
    for a in A:
        x = Needs[a]
        if t-x>=0:
            if dp[t-x]+1 == dp[t]:
                W[V[x]] += 1
                t -= x
                break
for i in range(9,0,-1):
    ans += str(i)*W[i]
print(ans)
def kaijo(n):
  if n ==1:
    return n
  return n * kaijo(n-1)

n = int(input())

print(kaijo(n)%1000000007)


### FIXED CODE ###

#再帰関数作ったら再帰回数の上限を超えてエラーになったっぽい
"""
def kaijo(n):
  if n ==1:
    return n
  return n * kaijo(n-1)
"""

import math

n = int(input())

print(math.factorial(n)%1000000007)

#print(kaijo(n)%1000000007)
x,y,z = int().split(',')
print(x,y,z)

### FIXED CODE ###

x, y, z = input().split(',')
print(x, y, z)
h,w = map(int,input().split())
L = []
for i in range(h):
  L.append(list(input()))
B = []
W = []
for i in range(h):
  for j in range(w):
    if L[i][j] == '.':
      W.append([i,j])
    else:
      B.append([i,j])
anslist = []
for i in range(len(W)):
  ans = float('inf')
  for j in range(len(B)):
    if ans >= abs(W[i][0]-B[j][0])+abs(W[i][1]-B[j][1]):
      ans = abs(W[i][0]-B[j][0])+abs(W[i][1]-B[j][1])
  anslist.append(ans)
print(max(anslist))

### FIXED CODE ###

import collections
h,w = map(int,input().split())
q = collections.deque()
A = []
for i in range(h):
    s = input()
    L = []
    for j in range(w):
        if s[j] == '.':
            L.append(s[j])
        else:
            L.append(0)
            q.append([i,j])
    A.append(L)
dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]
while len(q) > 0:
    cur = q.popleft()
    for i in range(4):
        y = cur[0]+dy_dx[i][0]
        x = cur[1]+dy_dx[i][1]
        if 0 <= y < h and 0 <= x < w:
            if A[y][x] == '.':
                A[y][x] = A[cur[0]][cur[1]]+1
                q.append([y,x])
ans = 0
for i in range(h):
    for j in range(w):
        if ans < A[i][j]:
            ans = A[i][j]
print(ans)
n = int(input())
a = list(map(int, input().split()))

a.sort(reverse=True)
even = []
for i in range(n):
    if a[i] % 2 == 0:
        even.append(a[i])

three = 0
for i in range(len(even)):
    sub = even[i] * (3 ** three)
    while sub % 2 == 0:
        three += 1
        sub = sub / 2

print(three)

### FIXED CODE ###

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

a.sort(reverse=True)
even = []
for i in range(n):
    if a[i] % 2 == 0:
        even.append(a[i])

three = 0
for i in range(len(even)):
    sub = even[i]
    while sub % 2 == 0:
        three += 1
        sub = sub / 2

print(three)
a,b,c,d=map(int,input().split())

if a < 0:
    a = -a
if b < 0:
    b = -b
if c < 0:
    c = -c
if d < 0:
    d = -d

if a <= b:
    x = b
if c <= d:
    y = d

print(x*y)

### FIXED CODE ###

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

x1 = a*c
x2 = a*d
x3 = b*c
x4 = b*d

z = x1
if z < x2:
    z = x2
if z < x3:
    z = x3
if z < x4:
    z = x4

print(z)
n = int(input())
s = ''
while n > 0:
  n-=1
  ans += chr(ord('a') + n%26)
  n//=26
 
print(ans[::-1])
  

### FIXED CODE ###

n = int(input())
s = ''
while n > 0:
  n-=1
  s += chr(ord('a') + n%26)
  n//=26
 
print(s[::-1])
while True:
    H,W = map(int,input().split())
    if H == W == 0:
        break
    for i in range(H):
        if i = 1:
            print("#"*W)
        elif i = H:
            print("#"*W)
        else:
            print("#","・"*(W-2),"#")
    


### FIXED CODE ###

while True:
    H,W = map(int,input().split())
    
    if H == W == 0:
        break
    
    for i in range(H):
        if i == 0 or i == H-1:
            print('#' * W)
        else:
            print('#','.'*(W-2),'#',sep='')
    print('')
a,b=map(int,input().split())
ans=0
for i in range(a,b+1):
    s=list(str(i))
    k=0
    for j in range(5):
        k+=s[j]*(10**j)
    if i==k:
        ans+=1
print(ans)

### FIXED CODE ###

a,b=map(int,input().split())
ans=0
for i in range(a,b+1):
    s=list(str(i))
    k=0
    for j in range(5):
        k+=int(s[j])*(10**j)
    if i==k:
        ans+=1
print(ans)
n = int(input())
line = map(int,input().split())
box = []
for i in line:
  for j in range(1,10):
    if i % 2**j != 0:
      box.append(j - 1)
answer = min(box)
print(answer)

### FIXED CODE ###

def how_many(n):
  ans = 0
  while n % 2 == 0:
    n /= 2
    ans += 1
  return ans

n = int(input())
line = map(int , input().split())
answer = min(map(how_many , line))
             
print(answer)
a, b, c = int(input().split())

if a == b:
  print(c)
elif b == c:
  print(a)
elif a == c:
  print(b)

### FIXED CODE ###

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

if a == b:
  print(c)
elif b == c:
  print(a)
elif a == c:
  print(b)
N, M = map(int, input().split())
X = list(map(int, input().split()))
ans = 0
diff = []
 
X.sort()
 
for i in range(M-1):
  dif = X[i+1] -X[i]
  diff.append(dif)
  
diff.sort()
 
for n in range(N):
  diff.pop(-1)
 
for i in range(len(diff)):
  ans += diff[i]

print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
X = list(map(int, input().split()))
ans = 0
diff = []
 
X.sort()
 
if (N < M): 
    for i in range(M-1):
        dif = X[i+1] - X[i]
        diff.append(dif)
    
    diff.sort()
    
    for i in range(M-N):
        ans += diff[i]
    # for n in range(N):
    #     diff.pop(-1)
   
    # for i in range(len(diff)):
    #     ans += diff[i]
print(ans)
h, w = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(h)]

INF = float('inf')
costs = [[0 for _ in range(w)] for _ in range(h)]


def dfs(i, j, paths, count):
    costs[i][j] = INF
    if ls[i][j] % 2 == 1 and count > 1:
        return paths
    if min([min(c) for c in costs]) == INF:
        return []
    if j > 0 and costs[i][j - 1] < INF:
        paths.append((i, j, i, j - 1))
        paths = dfs(i, j - 1, paths, count + 1)
    elif i < h - 1 and costs[i + 1][j] < INF:
        paths.append((i, j, i + 1, j))
        paths = dfs(i + 1, j, paths, count + 1)
    elif j < w - 1 and costs[i][j + 1] < INF:
        paths.append((i, j, i, j + 1))
        paths = dfs(i, j + 1, paths, count + 1)
    elif i > 0 and costs[i - 1][j] < INF:
        paths.append((i, j, i - 1, j))
        paths = dfs(i - 1, j, paths, count + 1)
    else:
        pi, pj, _, _ = paths.pop()
        paths = dfs(pi, pj, paths, count - 1)
    return paths


res = []
for i in range(h):
    for j in range(w):
        if costs[i][j] < INF and ls[i][j] % 2 == 1:
            paths = dfs(i, j, [], 1)
            if len(paths) > 0:
                res += paths
print(len(res))
for row in res:
    row = map(lambda x: x + 1, row)
    print(*row)

### FIXED CODE ###

h, w = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(h)]
ls = [[bool(a % 2) for a in l] for l in ls]

res = []
started = False
steps = []
for i in range(h):
    odd = i % 2
    for j in range(w):
        if odd:
            j = w - j - 1
        if started:
            steps.append((i, j))
        if ls[i][j]:
            if not started:
                steps = [(i, j)]
                started = True
            else:
                for s, t in zip(steps, steps[1:]):
                    res.append((s[0], s[1], t[0], t[1]))
                started = False

print(len(res))
for row in res:
    row = map(lambda x: x + 1, row)
    print(*row)
n = int(input())
s = input()
k = int(input())

for i in range(n):
    if s[i]!=s[k]:
        s = s.replace(s[i], '*')
print(s)


### FIXED CODE ###

n = int(input())
s = input()
k = int(input())

for i in range(n):
    if s[i]!=s[k-1]:
        s = s.replace(s[i], '*')
print(s)
import sys

n = input()
n= int(n)
ls = input().split()
lsnum = list(map(int,ls))
ma = max(lsnum)

minvalue = 100000000
ans = -1
for num in lsnum:
    value = abs(ma/2-num)
    if minvalue >= value:
        minvalue = value
        ans = [ma, num]
print (ans[0], ans[1])


### FIXED CODE ###

import sys

n = input()
n= int(n)
ls = input().split()
lsnum = list(map(int,ls))
ma = max(lsnum)

minvalue = 10000000000
ans = -1
for num in lsnum:
    if num == ma:
        continue
    value = abs(ma-num*2)
    if minvalue >= value:
        minvalue = value
        ans = [ma, num]
print (ans[0], ans[1])
n,Q=map(int,input().split())
s=input()

a=[0]*(n+1)
for i in range(n):
    if s[i]=='A' and s[i+1]=='C':
        a[i+1]=a[i]+1
    else:
        a[i+1]=a[i]

print(a)
for i in range(Q):
    l,r=map(int,input().split())
    print(a[r-1]-a[l-1])

### FIXED CODE ###

n,Q=map(int,input().split())
s=input()

a=[0]*(n+1)
for i in range(2,n+1):
    if s[i-2]=='A' and s[i-1]=='C':
        a[i]=a[i-1]+1
    else:
        a[i]=a[i-1]

for i in range(Q):
    l,r=map(int,input().split())
    print(a[r]-a[l])
n, m = (int(i) for i in input().split())
p = [None] * m
s = [None] * m
for i in range(m):
    p[i], s[i] = (j for j in input().split())
    p[i] = int(p[i])
    
pena = [0] * m
ac   = [0] * m
for i in range(m):
    q_index = p[i]-1
    if s[i] == 'AC': 
        ac[q_index] = 1
    if s[i] == 'WA':
        if ac[q_index] == 0: pena[q_index] += 1
        
print(sum(ac), sum(pena))

### FIXED CODE ###

n, m = (int(i) for i in input().split())
p = [None] * m
s = [None] * m
for i in range(m):
    p[i], s[i] = (j for j in input().split())
    p[i] = int(p[i])
    
pena = [0] * n
ac   = [0] * n

for i in range(m):
    q_index = p[i]-1
    if s[i] == 'AC': 
        ac[q_index] = 1
    if s[i] == 'WA':
        if ac[q_index] == 0: pena[q_index] += 1
        
ac_num = 0
pena_num = 0
for i in range(n):
    if ac[i] == 1:
        ac_num += 1
        pena_num += pena[i]

print(ac_num, pena_num)
# 初期入力
import numpy as np 
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort()
A_np =np.array(A,dtype=np.int64)
A_set =set(A)
count =set()
for i in range(N):
    if np.count_nonzero(A[i] %A_np[:i] ==0) >=1:
            count.add(A[i])
ans =len(A_set - count)
print(ans)
"""

### FIXED CODE ###


2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

	

from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))
cnt = Counter(A)
A.sort()
ans = 0
MX = 10**6
P = [0] * (MX+1)
for a in A:
    if P[a]==0:
        for i in range(MX+1):
            x = a*i
            if x > MX:
                break
            P[x] = 1
        if cnt[a]==1:
            ans+=1
print (ans)
import math
n.d=map(int,input().split())
x=d*2+1
print(math.ceil(n/x))

### FIXED CODE ###

import math
n,d=map(int,input().split())
x=d*2+1
print(math.ceil(n/x))
# https://atcoder.jp/contests/abc137/tasks/abc137_c

import math

N = int(input())

s_dic = {}
s_set = set()

for i in range(N):
    s = input()

    s = ''.join(sorted(s))

    if s in s_set:
        s_dic[s] += 1

    else:
        s_set.add(s)
        s_dic[s] = 1


result = 0

for val in s_dic.values():

    if val > 1:
        result += int(math.factorial(val) /2)

print(result)

### FIXED CODE ###

# https://atcoder.jp/contests/abc137/tasks/abc137_c

import math

N = int(input())

s_dic = {}
s_set = set()

for i in range(N):
    s = input()

    s = ''.join(sorted(s))

    if s in s_set:
        s_dic[s] += 1

    else:
        s_set.add(s)
        s_dic[s] = 1


result = 0

for val in s_dic.values():

    if val > 1:
        result += int((val * (val - 1)) / 2)

print(result)
num = input()

answer = num + num * num + num * num * num

### FIXED CODE ###

num = int(input())
 
answer = num + num * num + num * num * num
 
print(answer)
n,k = map(int,input().split())
s = input()
ss = s.lower()
if k == 1:
  print(ss[0]+s[1:n])
elif k == n:
  print(s[0:n-1]+ss[n])
else:
  print(s[0:k-1]+ss[k]+s[k+1:n])

### FIXED CODE ###

n,k = map(int,input().split())
s = input()
ss = s.lower()
if k == 1:
  print(ss[0]+s[1:n])
elif k == n:
  print(s[0:n-1]+ss[n-1])
else:
  print(s[0:k-1]+ss[k-1]+s[k:n])
S=1729

def f(n): 
      
    # single line to find factorial 
    return 1 if (n==1 or n==0) else n * f(n - 1);

possibles=0

n=10**9+7
biggest_sub=S//3
for i in range(1,biggest_sub+1):
	possibles+=f(S-3*i+i-1)/f(i-1)/f(S-3*i)
	possibles%=n

n=10**9+7
print(possibles%n)

### FIXED CODE ###

#import sys
#input = sys.stdin.readline
Q = 10**9+7
def cmb(n,r):
    if n-r < r: r = n-r
    if r == 0: return 1
    denominator = 1                       #分母
    numerator = 1                         #分子
    for i in range(r):
        numerator *= n-i
        numerator %= Q
        denominator *= i+1
        denominator %= Q
    return numerator*pow(denominator, Q-2, Q)%Q
 
def main():
    S = int( input())
    ans = 0
    for i in range(1, S//3+1):
        t = S - i*3
        ans += cmb(t+i-1,i-1)
        ans %= Q
    print(ans)
        
if __name__ == '__main__':
    main()
n = int(input())
s = input()
ans = 0
for i in range(n):
    if s[i] == "A":
        if s[i+1] == "B":
            if s[i+2] == "C":
                ans += 1
print(ans)

### FIXED CODE ###

n = input()
s = input()
print(s.count("ABC"))
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():

    # Python3で出すことに注意！
    # floyd_warshall

    # https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.floyd_warshall.html
    # ↑を見ながら細部を埋める
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra

    # (i, j)成分はiからjへの直接経路のコスト
    N=int(input())
    graph = [[0]*N for i in range(N)]
    for i in range(N-1):
        a,b,c=map(int,input().split())
        graph[a-1][b-1]=c


    graph = csr_matrix(graph)

    dist_matrix = dijkstra(csgraph=graph, directed=False, return_predecessors=False)
    # (i, j)成分はiからjへの最短コスト
    Q,K=map(int,input().split())
    for i in range(Q):
        x,y=map(int,input().split())
        print(int(dist_matrix[x-1][K-1]+dist_matrix[K-1][y-1]))


resolve()

### FIXED CODE ###

import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        Edge[a-1].append((b-1, c))
        Edge[b-1].append((a-1, c))
    Q, K = map(int, input().split())
    q = deque()
    Dist = [-1] * N
    q.append((K-1, K-1, 0))
    while q:
        nowN, preN, nD = q.popleft()
        if Dist[nowN] == -1:
            Dist[nowN] = nD
            for e, add in Edge[nowN]:
                if e != preN: q.append((e, nowN, nD + add))
    Ans = [None] * Q
    for i in range(Q):
        x, y = map(int, input().split())
        Ans[i] = str(Dist[x-1] + Dist[y-1])
    print("\n".join(Ans))

    return 0

if __name__ == "__main__":
    solve()
print(max(A + B,A - B,A * B))

### FIXED CODE ###

A,B = map(int,input().split())
print(max(A + B, A - B,A * B))
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
input = sys.stdin.buffer.readline


sys.setrecursionlimit(10**9)
from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

#

def main():
	mod=10**9+7
	n=II()
	G=[[] for _ in range(n+1)]
	e=[]
	v=[0]*(n+1)
	p=[0]*(n+1)

	for _ in range(n-1):
		a,b=MI()
		G[a].append(b)
		G[b].append(a)
		e.append([a,b,0])

	@lru_cache(maxsize=None)
	def tree(a):
		cnt=1
		for i in G[a]:
			if p[a]==i:
				continue
			else:
				p[i]=a
				cnt+=tree(i)
		v[a]=cnt
		return cnt
	tree(1)
	#print(v)

	for i in range(n-1):
		#print(e[i])
		a=e[i][0]
		b=e[i][1]
		e[i][2]=min(v[a],v[b])
	#print(e)

	ex=0

	for _,_,c in e:
		ex+=(1-0.5**c)*(1-0.5**(n-c))
	ex+=1-0.5**n-n/2
	ex=int(ex*2**n+0.5)
	#print(ex)

	for i in range(1,n+1):
		if ex%2==0:
			ex//=2
		else:
			i-=1
			break
	y=ex
	x=2**(n-i)
	#print(y,x)

	y%=mod
	x%=mod

	ans=y*pow(x,mod-2,mod)%mod

	print(ans)





































if __name__ == "__main__":
	main()

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
input = sys.stdin.buffer.readline


sys.setrecursionlimit(10**9)
from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

#

def main():
	mod=10**9+7
	n=II()
	G=[[] for _ in range(n+1)]
	p=[0]*(n+1)
	v=[0]*(n+1)


	for _ in range(n-1):
		a,b=MI()
		G[a].append(b)
		G[b].append(a)

	inv2=[1]*(n+1)
	t=pow(pow(2,n,mod),mod-2,mod)
	for i in range(n,-1,-1):
		inv2[i]=t
		t*=2
		t%=mod
	#print(inv2)

	def dfs(a):
		cnt=1
		for i in G[a]:
			if p[a]==i:
				continue
			else:
				p[i]=a
				cnt+=dfs(i)
		v[a]=cnt
		return cnt
	dfs(1)
	#print(v)

	def f(a):
		return (1-inv2[a])*(1-inv2[n-a])%mod

	ans=1-inv2[n]-n*inv2[1]
	for i in range(1,n+1):
		ans+=f(v[i])%mod
	print(ans%mod)



if __name__ == "__main__":
	main()