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

# B
import numpy as np
np.random.seed(71)
from collections import deque
# input
N, M = map(int, input().split())
G = dict()
for n in range(1, N+1):
    G[n] = []

for _ in range(M):
    A, B = map(int, input().split())
    G[A].append(B)
    G[B].append(A)
    
# find minimum degree
s = np.argmin(np.array([len(G[k]) for k in range(1, N+1)])) + 1

targets = dict()
for a in G[s]:
    targets[a] = 1


# BFS from st
t = G[s][0]
pt = [s, t]
del targets[t]
while len(targets) > 0:
    ques = deque()
    visited = [0]*(N+1)    
    for a in pt:
        visited[a] = 1
    ques.append([t, pt])
    end = 0
    while len(ques) > 0 and end == 0:
        q = ques.popleft()
        s = q[0]
        pt = q[1]
        for t in G[s]:
            if visited[t] == 1:
                pass
            elif t in targets.keys():
                pt.append(t)
                end = 1
                del targets[t]
                break
            else:
                visited[t] = 1
                ques.append([t, pt+[t]])
            

# BFS from end
visited = [0]*(N+1)
for a in pt:
    visited[a] = 1
sv = np.array([len([l for l in G[k] if visited[l] == 0]) if visited[k] == 0 else N for k in range(1, N+1)])

# need calculation
if len([l for l in G[t] if visited[l] == 0]) != 0:
    endp = np.random.choice(np.arange(N)[sv == min(sv)]) + 1
    targets = dict()
    for a in G[endp]:
        if visited[a] == 0:
            targets[a] = 1
    while len(targets) > 0:
        ques = deque()
        visited = [0]*(N+1)    
        for a in pt:
            visited[a] = 1
        visited[endp] = 1
        ques.append([t, pt])
        end = 0
        while len(ques) > 0 and end == 0:
            q = ques.popleft()
            s = q[0]
            pt = q[1]
            for t in G[s]:
                if visited[t] == 1:
                    pass
                elif t in targets.keys():
                    pt.append(t)
                    end = 1
                    del targets[t]
                    break
                else:
                    visited[t] = 1
                    ques.append([t, pt+[t]])
    pt.append(endp)
        
print(len(pt))
print(" ".join([str(a) for a in pt]))

### FIXED CODE ###

# B
import numpy as np
from collections import deque
# input
N, M = map(int, input().split())
G = dict()
for n in range(1, N+1):
    G[n] = []
    
visited = [0]*(N+1)
for m in range(M):
    A, B = map(int, input().split())
    G[A].append(B)
    G[B].append(A)
    if m == 0:
        pt = [A, B]
        visited[A] = 1
        visited[B] = 1

# from left
s = pt[0]
add_left = list()

while True:
    left_ext = [l for l in G[s] if visited[l] == 0]
    if len(left_ext) != 0:
        s = left_ext[0]
        visited[s] = 1
        add_left.append(s)
    else:
        break

# from right
s = pt[1]
add_right = list()

while True:
    right_ext = [l for l in G[s] if visited[l] == 0]
    if len(right_ext) != 0:
        s = right_ext[0]
        visited[s] = 1
        add_right.append(s)
    else:
        break
pt = list(reversed(add_left)) + pt + add_right
print(len(pt))
print(" ".join([str(a) for a in pt]))
### BUGGY CODE ###

buf=[-1 for i in range(90)]
def ryuka(N):
    global buf
    if buf[N]!=-1:
        return buf[N]
    else:
        if N==1:
            return 1
        elif N==0:
            return 2
        else:
            return ryuka(N-1)+ryuka(N-2)

N=int(input())
print(ryuka(N))



### FIXED CODE ###

buf=[-1 for i in range(90)]
def ryuka(N):
    global buf
    if buf[N]!=-1:
        return buf[N]
    else:
        if N==1:
            return 1
        elif N==0:
            return 2
        else:
            buf[N]=ryuka(N-1)+ryuka(N-2)
            return ryuka(N-1)+ryuka(N-2)

N=int(input())
print(ryuka(N))
### BUGGY CODE ###

n = int(input())
s = list(input() for _ in range(n))

a = []
a_num = []

for i in range(n):
    if s[i] not in a:
        a.append(s[i])
        a_num.append(0)
    else:
        a_num[a.index(s[i])] += 1

ans_num = max(a_num)
ans = []

for i in range(len(a)):
    if a_num[i] == ans_num:
        ans.append(a[i])
ans.sort()
print("\n".join(ans))

### FIXED CODE ###

from collections import Counter

n = int(input())
s_list = sorted(list(input() for _ in range(n)))

s = Counter(s_list)

ans_num = s.most_common(1)[0][1]

s_1 = sorted(list(s.items()), key=lambda x: x[0])

for i in range(len(s_1)):
    if s_1[i][1] == ans_num:
        print(s_1[i][0])
### BUGGY CODE ###

import itertools 
import copy
import math
from functools import reduce

num = int(input())
a_list = [i for i in range(1,num+1)]
b_list = a_list.copy()
c_list = a_list.copy()
comb_list = list(itertools.product(a_list,b_list,c_list))

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

sum_yaku = 0
for i in comb_list:
    num_list = list(i)
    sum_yaku += gcd_list(num_list)
print(sum_yaku)

### FIXED CODE ###

import itertools 
import math
from functools import reduce


num = int(input())

def gcd_list(numbers):
        return reduce(math.gcd, numbers)

if num<=2:
    a_list = [i for i in range(1,num+1)]
    comb_list = list(itertools.product(a_list, repeat=3))
    print(sum([gcd_list(x) for x in comb_list]))

else:
    a_list = [i for i in range(1,num+1)]
    comb_list = list(itertools.combinations_with_replacement(a_list, 3))
    test = sum([gcd_list(x) for x in comb_list])*3

    comb_list_dup = [[i, i, i] for i in a_list]
    duplica = sum([gcd_list(x) for x in comb_list_dup])*2

    comb_list_unique = list(itertools.combinations(a_list, 3))
    unique = sum([gcd_list(x) for x in comb_list_unique])*3
    print(test-duplica+unique)
### BUGGY CODE ###

n,k=map(int,input().split())
ps=list(map(int,input().split()))
res=max(sum(ps[i:i+k]) for i in range(n-k+1))
print((res+k)/2)

### FIXED CODE ###

n,k=map(int,input().split())
ps=list(map(int,input().split()))
tmp=sum(ps[:k])
res=tmp
for p,s in zip(ps,ps[k:]):
  tmp+=s-p
  res=max(res,tmp)
print((res+k)/2)
### BUGGY CODE ###

def find_gcd(x, y): 
    while(y): 
        x, y = y, x % y 
  
    return x 
K = int (input())
sum = 0

for i in range (1, K+1):
    for j in range (1, K+1):
        for k in range (1, K+1):
            sum += find_gcd(i, find_gcd(j,k))

print (sum)

### FIXED CODE ###

import math

t = int (input())
sum = 0

for i in range (1, t+1):
    for j in range (1, t+1):
        aux = math.gcd(i,j)
        for k in range (1, t+1):
            sum += math.gcd(aux, k)

print (sum)
### BUGGY CODE ###

def factorial_power(n):
    power = 1
    for i in range(1, n + 1):
        power *= i
    return power

divisor = (10 ** 9) + 7

N = int(input())

print(factorial_power(N) % divisor)

### FIXED CODE ###

def factorial_power(n):
    power = 1
    
    for i in range(1, n+1):
        power *= i
        power = power % divisor
    return power

divisor = (10 ** 9) + 7

N = int(input())

print(factorial_power(N))
### BUGGY CODE ###

N = int(input())
D = list(map(int, input().split()))
ans = 0
for i in range(min(D), max(D)) :
  cnt = len(list(filter(lambda x : x <= i, D)))
  if(cnt == N // 2) :
    ans += 1
  elif(cnt > N // 2) :
    break
  else :
    pass
print(ans)

### FIXED CODE ###

N = int(input())
D = list(map(int, input().split()))
D.sort()
ans = 0
for i in range(N // 2) :
  cnt = len(list(filter(lambda x : x <= D[N // 2 - 1 + i], D)))
  if(cnt == N // 2) :
    ans += D[N // 2] - D[N // 2 - 1]
  elif(cnt > N // 2) :
    break
  else :
    pass
print(ans)
### BUGGY CODE ###

n1, n2 = [int(i) for i in input().split()]
n3 = [int(i) for i in input().split()]

n3.sort()
for i1 in range(n2):
    n3[n1 - 1] = n3[n1 - 1] // 2
    n3.sort()

r1 = 0
for i2 in range(n1):
    r1 += n3[i2]

print(r1)

### FIXED CODE ###

n1, n2 = [int(i) for i in input().split()]
n3 = [int(i) for i in input().split()]

n3.sort(reverse = True)

c1 = 0
while True:
    n3[0] = n3[0] // 2
    c1 += 1
    if c1 >= n2:
        break
    t2 = 1
    while len(n3) != 1:
        if n3[t2] >= n3[0]:
            n3[t2] = n3[t2] // 2
            t2 += 1
            c1 += 1
            if c1 >= n2 or t2 >= len(n3):
                break
        else:
            break

    if c1 >= n2:
        break

    n3.sort(reverse = True)

r1 = 0
for i2 in range(n1):
    r1 += n3[i2]

print(r1)
### BUGGY CODE ###

def main():
    import sys
    from copy import deepcopy
    input = sys.stdin.readline
    R, C, K = [int(x) for x in input().strip().split()]
    G = [[0] * (C+1) for r in range(R+1)]
    for k in range(K):
        r, c, v = [int(x) for x in input().strip().split()]
        G[r][c] = v
    # for r in range(R+1):
    #     print(G[r])
    ans = [[[0] * 4 for _ in range(C+1)] for _ in range(R+1)]
    for r in range(1, R+1):
        for c in range(1, C+1):
            ans[r][c][0] = max(ans[r-1][c][-1], ans[r][c-1][0])
            for i in range(1, 4):
                ans[r][c][i] = max(ans[r-1][c][3], ans[r][c-1][i], ans[r-1][c][3]+G[r][c], ans[r][c-1][i-1]+G[r][c])

    print(max(ans[-1][-1]))

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    from copy import deepcopy
    input = sys.stdin.readline
    R, C, K = [int(x) for x in input().strip().split()]
    G = [[0] * (C+1) for r in range(R+1)]
    for k in range(K):
        r, c, v = [int(x) for x in input().strip().split()]
        G[r][c] = v
    # for r in range(R+1):
    #     print(G[r])
    ans = [[[0] * 4 for _ in range(C+1)] for _ in range(2)]
    for r in range(1, R+1):
        for c in range(1, C+1):
            ans[r%2][c][0] = max(ans[(r-1)%2][c][-1], ans[r%2][c-1][0])
            for i in range(1, 4):
                ans[r%2][c][i] = max(ans[(r-1)%2][c][3], ans[r%2][c-1][i], ans[(r-1)%2][c][3]+G[r][c], ans[r%2][c-1][i-1]+G[r][c])

    print(max(ans[R%2][-1]))

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

import sys
n = int(input())
a_ls = [int(i) for i in sys.stdin.readline().split()]
b_ls = []
for i, a in enumerate(a_ls):
    if i % 2 == 0:
        b_ls.append(a)
    else:
        b_ls = [a] + b_ls
if n % 2 == 1:
    b_ls.reverse()
print(" ".join([str(i) for i in b_ls]))

### FIXED CODE ###

import sys
from collections import deque
n = int(input())
a_ls = [int(i) for i in sys.stdin.readline().split()]
b_ls = deque([])
for i, a in enumerate(a_ls):
    if i % 2 == 0:
        b_ls.append(a)
    else:
        b_ls.appendleft(a)
if n % 2 == 1:
    b_ls.reverse()
print(" ".join([str(i) for i in b_ls]))
### BUGGY CODE ###

def main(n):
  if n<6:
    print(n)
    exit()
  l=[6**i for i in range(7)]
  l[6:6]=[9**i for i in range(1,6)]
  l.sort()
  if n in l:
    print(1)
    exit()
  from collections import deque
  todo=deque([[1,li] for li in l[1:] if n>li])
  while len(todo)>0:
    d=todo.popleft()
    t0=d[0]
    t1=d[1]
    for li in [li for li in l if li<=n-d[1]]:
      if t1+li==n:
        print(t0+1)
        exit()
      else:
        todo.append([t0+1,t1+li])

if __name__=='__main__':
  import sys
  input = sys.stdin.readline
  n=int(input())
  main(n)

### FIXED CODE ###

def dfs(a,b,c):
  todo=[[]]
  ret=[]
  while len(todo)>0:
    t=todo.pop()
    l=len(t)
    if l==a:
      ret.append(t)
    else:
      s=0
      for i in range(1,l+1):
        s+=6**i*t[i-1]
      for i in range(b+1):
        if s+6**(l+1)*i<=c:
          tc=t.copy()
          tc.append(i)
          todo.append(tc)
  return ret
a=6
b=5
c=int(input())
l=dfs(a,b,c)
ans=c
for li in l:
  ansi=sum(li)
  now=c-sum([6**(i+1)*li[i]for i in range(len(li))])
  for i in range(1,7):
    ansi+=now%9
    now//=9
  ans=min(ans,ansi)
print(ans)
### BUGGY CODE ###

#b
r, g, b, n = (int(_) for _ in input().split())
red = n // r
sets = []
ans = 0
for i in range(red + 1):
    remainder = n - (r*i)
    green = remainder // g
    if remainder == 0:
        ans += 1
    else:
        for j in range(green+1):
            nremainder = remainder - j*g
            if nremainder == 0:
                ans += 1
            elif nremainder > 0 and nremainder % b == 0:
                k = nremainder // b
                ans += 1

print(ans)

### FIXED CODE ###

#b
r, g, b, n = (int(_) for _ in input().split())
red = n // r
sets = []
ans = 0
for i in range(red + 1):
    remainder = n - (r*i)
    green = remainder // g
    if remainder == 0:
        ans += 1
    else:
        for j in range(green+1):
            nremainder = remainder - j*g
            if nremainder == 0:
                ans += 1
            elif nremainder > 0 and nremainder % b == 0:
                k = nremainder // b
                ans += 1

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

def solve(i, m):
    if m == 0: return True
    if i == n or m < 0:
        return False

    r1 = solve(i + 1, m)
    r2 = solve(i + 1, m - A[i])

    return r1 or r2


n = int(raw_input())
A = map(int, raw_input().split())

q = int(raw_input())
M = map(int, raw_input().split())

for i in M:
    print "yes" if solve(0, i) else "no"

### FIXED CODE ###

def solve(i, m):
    if m == 0: return True

    if i < n and min(A[i:]) <= m <= sum(A[i:]):
        r1 = solve(i + 1, m-A[i])
        if r1: return r1
        r2 = solve(i + 1, m)
        if r2: return r2


n = int(raw_input())
A = map(int, raw_input().split())

q = int(raw_input())
M = map(int, raw_input().split())

for i in M:
    print "yes" if solve(0, i) else "no"
### BUGGY CODE ###

s=input()
n=len(s)
while '10' in s:
    s=s.replace('10','')
while '01' in s:
    s=s.replace('01','')
print(n-len(s))

### FIXED CODE ###

s=input()
print(len(s)-abs(s.count('1')-s.count('0')))
### BUGGY CODE ###

from heapq import heapify, heappop, heappush

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

q = [(-val, i) for i, val in enumerate(b) if val != a[i]]
heapify(q)

# 3print(q)

cnt = 0

while q:
  bval, i = heappop(q)
  bval = - bval - a[i]
  dv, bval = divmod(bval, b[i - 1] + b[(i + 1) % n])
#   print(dv, bval,i)
  if dv == 0:
    print(-1)
    exit()
  bval += a[i]
  b[i] = bval
  cnt += dv
  if bval != a[i]:
    heappush(q, (- bval, i))
print(cnt)

### FIXED CODE ###

from heapq import heapify, heappop, heappush

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

q = [(-val, i) for i, val in enumerate(b) if val != a[i]]
heapify(q)

# 3print(q)

cnt = 0

while q:
  bval, i = heappop(q)
  bval = - bval - a[i]
  dv, bval = divmod(bval, b[i - 1] + b[(i + 1) % n])
#   print(dv, bval,i)
  if dv == 0:
    print(-1)
    exit()
  bval += a[i]
  b[i] = bval
  cnt += dv
  if bval != a[i]:
    heappush(q, (- bval, i))
print(cnt)
### BUGGY CODE ###

import array

n= int(input())

maxN = 1000000
a = list(map(int, input().split()))

def calculate_prime():
    primes = [True] * maxN
    primes[0] = primes[1] = False
    prim = []
    prime_map = dict()
    for i in range(2, maxN):
        if primes[i] == True:
            prime_map[i] = 0
            prim.append(i)
            j = i * i
            while j < maxN:
                primes[j]= False
                j+=i
    return prime_map, array.array('i',prim)

prime_map, prim = calculate_prime()

#print(prim)
for i in a:
    if i in prime_map:
        if prime_map[i] < 1:
            prime_map[i] = 1
    else:
        k = i
        for j in prim:
            if k % j == 0:
                tmp = 0
                while k % j == 0:
                    k = k // j
                    tmp += 1
                if tmp > prime_map[j]:
                    prime_map[j] = tmp
            if k in prime_map:
                if prime_map[k] < 1:
                    prime_map[k] = 1
                    break
            if k == 1:
                break

lcm = 1
for k, v in prime_map.items():
    if v > 0:
        lcm = lcm * (k**v)

#print(lcm)
result = 0

for i in a:
    result += lcm // i
    if result >= 1000000007:
        result = result % 1000000007

print(result)


### FIXED CODE ###

import array

n= int(input())

maxN = 1000000
a = list(map(int, input().split()))

def calculate_prime():
    primes = [True] * maxN
    primes[0] = primes[1] = False
    prim = []
    prime_map = dict()
    for i in range(2, maxN):
        if primes[i] == True:
            prime_map[i] = 0
            prim.append(i)
            j = i * i
            while j < maxN:
                primes[j]= False
                j+=i
    return prime_map, array.array('i',prim)

prime_map, prim = calculate_prime()

pppp = []
#print(prim)
for i in list(set(a)):
    if i in prime_map:
        if prime_map[i] < 1:
            pppp.append(i)
            prime_map[i] = 1

    else:
        k = i
        for j in prim:
            if k % j == 0:
                tmp = 0
                while k % j == 0:
                    k = k // j
                    tmp += 1
                if tmp > prime_map[j]:
                    if prime_map[j] == 0:
                        pppp.append(j)
                    prime_map[j] = tmp
            if k in prime_map:
                if prime_map[k] < 1:
                    pppp.append(k)
                    prime_map[k] = 1
                    break
            if k == 1:
                break

lcm = 1
for k in list(set(pppp)):
    lcm = lcm * (k**prime_map[k])

#print(lcm)
result = 0

for i in a:
    result += lcm // i

if result >= 1000000007:
    result = result % 1000000007
print(result)
### BUGGY CODE ###

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

L = []
R = []
for i, A in enumerate(A_list):
    L.append(i+A)
    R.append(i-A)

ans = 0
for l in L:
    ans += R.count(l)

print(ans)


### FIXED CODE ###

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

L = []
R = []
for i, A in enumerate(A_list):
    L.append(i+A)
    R.append(i-A)


import collections
r_dict = collections.Counter(R)
ans = 0
for l in L:
    ans += r_dict.get(l, 0)
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a = []
dp = [0]
mod = 10**9+7

for i in range(m):
    a.append(int(input()))

if 1 in a and 2 in a:
    dp.append(0)
    dp.append(0)
    print(0)
    exit()
elif 1 in a and 2 not in a:
    dp.append(0)
    dp.append(1)
elif 1 not in a and 2 in a:
    dp.append(1)
    dp.append(0)
else:
    dp.append(1)
    dp.append(2)

for i in range(3, n+1):
    if i in a:
        dp.append(0)
    else:
        dp.append((dp[i-1] + dp[i-2]) % mod)

print(dp[n])






### FIXED CODE ###

n, m = map(int, input().split())
a = []
# dp = [0]*(n+1)
dp = [None]*(10**5+1)
mod = 10**9+7
dp[0] = 0

for i in range(m):
    ng = int(input())
    a.append(ng)
    dp[ng] = 0

if 1 in a and 2 in a:
    print(0)
    exit()
elif 1 in a and 2 not in a:
    dp[1] = 0
    dp[2] = 1
elif 1 not in a and 2 in a:
    dp[1] = 1
    dp[2] = 0
else:
    dp[1] = 1
    dp[2] = 2

for i in range(3, n+1):
    if dp[i] is None:
        dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[n])
### BUGGY CODE ###

n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

k = min(n-1, k)

inf = 100000000

dp = [inf for _ in [0]*n]

def cost(i, j):
	return abs(h[i] - h[j])

for i in range(k+1):
	dp[i] = cost(0, i)

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

print(dp[-1])


### FIXED CODE ###

n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

k = min(n-1, k)

inf = 100000000

dp = [inf for _ in [0]*n]

def cost(i, j):
	return abs(h[i] - h[j])

for i in range(k+1):
	dp[i] = cost(0, i)

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

print(dp[-1])
### BUGGY CODE ###

from collections import deque

N, M = map(int, input().split())
Edge = [[] for _ in range(N)]
Start = {a for a in range(N)}
End = set()
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    Edge[x].append(y)
    End.add(y)
Start = Start - End
Q = deque(Start)

DP = [0] * N
ans = 0
while Q:
    now = Q.popleft()
    for nex in Edge[now]:
        if DP[nex] < DP[now] + 1:
            DP[nex] = DP[now] + 1
            Q.append(nex)
            ans = DP[nex]
print(ans)



### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N, M = map(int, input().split())
Edge = [[]for _ in range(N)]
Far = [-1]*N
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    Edge[x].append(y)


def long(x):
    if len(Edge[x]) == 0:
        Far[x] = 0
        return 0
    if Far[x] >= 0:
        return Far[x]
    r = 0
    for i in Edge[x]:
        l = long(i) + 1
        r = max(r, l)
    Far[x] = r
    return r


for i in range(N):
    long(i)
print(max(Far))
### BUGGY CODE ###

n, k = map(int, input().split())
h_list = list(map(int, input().split()))
cost_list = [0, abs(h_list[0] - h_list[1])]
for i in range(2, n):
    cost = 10**9
    for j in range(max(i-k, 0), i):
        cost = min(cost, abs(h_list[j] - h_list[i]) + cost_list[j])
    cost_list.append((cost))
print(cost_list[-1])


### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
h_arr = np.array(list(map(int, input().split())))
cost_arr = np.zeros(n, dtype=int)
for i in range(1, n):
    start = max(i-k, 0)
    cost_arr[i] = (abs(h_arr[start:i] - h_arr[i]) + cost_arr[start:i]).min()
print(int(cost_arr[-1]))
### BUGGY CODE ###

import sys 
sys.setrecursionlimit(10**9)
N = int(input())
G = [[] for _ in range(N)]
mod = 10**9+7
for _ in range(N-1):
    A, B = map(int, input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
cnt = [[] for _ in range(N)]
def dfs(p, v, n):
    s = 0
    for nv in G[v]:
        if nv == p:
            continue
        res = dfs(v, nv, n+1)
        cnt[v].append(res)
        s+=res
    cnt[v].append(N-s-1)
    return s+1
dfs(-1, 0, 0) 
ans = 0
p = [1]*N
for i in range(1, N):
    p[i] = p[i-1]*2%mod
for v in range(N):
    if len(cnt[v])<=1:
        continue    
    res = p[N-1]-1
    for a in cnt[v]:
        res-=p[a]-1
    ans+=res
    ans%=mod
inv = pow(2, (mod-2)*N, mod)
print(ans*inv%mod)







### FIXED CODE ###

import sys 
sys.setrecursionlimit(10**9)
N = int(input())
G = [[] for _ in range(N)]
mod = 10**9+7
for _ in range(N-1):
    A, B = map(int, input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
cnt = [[] for _ in range(N)]
que = [0]
depth = [-1]*N
depth[0] = 0
while que:
    v = que.pop()
    d = depth[v]
    for nv in G[v]:
        if depth[nv]>=0:
            continue
        depth[nv] = d+1
        que.append(nv)
d_to_i = [[] for _ in range(N)]
for i in range(N):
    d_to_i[depth[i]].append(i)
for d in range(N)[::-1]:
    for v in d_to_i[d]:
        for nv in G[v]:
            if depth[nv]<depth[v]:
                continue
            if cnt[nv]:
                cnt[v].append(sum(cnt[nv])+1)
            else:
                cnt[v].append(1)
for i in range(N):
    res = N-1
    for j in cnt[i]:
        res-=j
    cnt[i].append(res)
ans = 0
p = [1]*N
for i in range(1, N):
    p[i] = p[i-1]*2%mod
for v in range(N):
    if len(cnt[v])<=1:
        continue    
    res = p[N-1]-1
    for a in cnt[v]:
        res-=p[a]-1
    ans+=res
    ans%=mod
inv = pow(2, (mod-2)*N, mod)
print(ans*inv%mod)
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
count = 0

for i in range(N - 2):
    for j in range(N - i - 2):
        for k in range(N - i - j - 2):
            if L[i] < L[i + j + 1] + L[i + j + k + 2] and L[i + j + 1] < L[i + j + k + 2] + L[i] and L[i + j + k + 2] < L[i + j + 1] + L[i]:
                count = count + 1

print(count)

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
C = sorted(L)
count = 0

import bisect
for i in range(N - 2):
    for  j in range(N - i - 2):
        s = C[i] + C[j + i + 1]
        t = bisect.bisect_left(C,s)
        u = t - (j + i + 1) - 1
        if u <= 0:
            pass
        else:
            count = count + u

print(count)
### BUGGY CODE ###

a = input()
b = int(a)
s = []
while b > 0:
  t = b % 10
  s.append(t)
  b = b // 10
i = 0
while(a[i:i+1] == '0'):
  s.append(0)
  i += 1
s.reverse()
cnt = 0
if(len(s) == 1):
	cnt = 0
else:
	for i in range(len(s)-1):
		if(s[i] == s[i+1]):
			if(s[i] == 0):
				s[i+1] = 1
			else:
				s[i+1] = 0
			cnt += 1
print(cnt)

### FIXED CODE ###

s = input()
cnt = 0
if(s[:1] == '0'):
  for i in range(len(s) // 2):
    if(s[2*i+1:2*i+2] == '0'):
      cnt += 1
    if(s[2*i+2:2*i+3] == '1'):
      cnt += 1
else:
  for i in range(len(s) // 2):
    if(s[2*i+1:2*i+2] == '1'):
      cnt += 1
    if(s[2*i+2:2*i+3] == '0'):
      cnt += 1  
print(cnt)