CodeEff/ECCO huggingface dataset:
# Original solution
def f(k):
    T = S*k
    N = len(T)
    cur = T[0]
    cnt = 1
    ans = 0
    for i in range(1,N):
        if T[i]==cur:
            cnt += 1
        else:
            ans += cnt//2
            cur = T[i]
            cnt = 1
    ans += cnt//2
    return ans
S = input().strip()
K = int(eval(input()))
ans1 = f(1)
ans2 = f(2)
ans3 = f(3)
d1 = f(2)-f(1)
d2 = f(3)-f(2)
k = (K-1)//2
if (K-1)%2==0:
    print((f(1)+(d1+d2)*k))
else:
    print((f(1)+(d1+d2)*k+d1))

# Optimized solution
C = {}
S = input().strip()
N = len(S)
K = int(eval(input()))
for i in range(N):
    s = S[i]
    if s not in C:
        C[s]=0
    C[s] += 1
if len(C)>1:
    a = 0
    cnt = 1
    for i in range(1,N):
        if S[i]==S[i-1]:
            cnt += 1
        else:
            a += cnt//2
            cnt = 1
    a += cnt//2
    X = S+S
    b = 0
    cnt = 1
    for i in range(1,2*N):
        if X[i]==X[i-1]:
            cnt += 1
        else:
            b += cnt//2
            cnt = 1
    b += cnt//2
    d = b-a
    print((a+d*(K-1)))
else:
    A = list(C.items())
    k = A[0][1]
    if k%2==0:
        print(((k//2)*K))
    else:
        if K%2==0:
            a = k
            b = 2*k
            d = k
            print((a+d*((K//2)-1)))
        else:
            a = k//2
            b = (k*3)//2
            d = b-a
            print((a+d*(K//2)))
# Original solution
from sys import stdin
from itertools import groupby
S = stdin.readline().rstrip()
K = int(stdin.readline().rstrip())
l = len(S)
# Run Length Encoding
rle = [len(list(g)) for k, g in groupby(S)]

if len(set(S)) == 1:
    print((len(S) * K //2))
else:
    tmp_ans = sum([l // 2 for l in rle])*K
    if S[0] != S[-1]:
        print(tmp_ans)
    else:
        print((tmp_ans - (rle[0] // 2 + rle[-1] // 2 - (rle[0] + rle[-1]) // 2) * (K-1)))

# Optimized solution
from sys import stdin
from itertools import groupby
S = stdin.readline().rstrip()
K = int(stdin.readline().rstrip())
l = len(S)
# Run Length Encoding
rle = [(k, sum(1 for _ in g)) for k, g in groupby(S)]

if len(set(S)) == 1:
    print((len(S) * K // 2))
else:
    tmp_ans = sum([t[1] // 2 for t in rle])*K
    if S[0] != S[-1]:
        print(tmp_ans)
    else:
        print((tmp_ans - (rle[0][1] // 2 + rle[-1][1] // 2 - (rle[0][1] + rle[-1][1]) // 2) * (K-1)))
# Original solution
from itertools import*
s,k=open(0)
k,x=int(k),0
g=[len(list(v))for _,v in groupby(s)]
for c in g:x+=c//2
x*=k
if(s[0]==s[-2])*g[0]%2&g[-2]%2:x+=k//2if-len(s)==~g[0]else k-1
print(x)

# Optimized solution
from itertools import*
s,k=open(0)
k=int(k)
g=[len(list(v))for _,v in groupby(s)]
print((sum(c//2for c in g)*k+((s[0]==s[-2])*g[0]%2&g[-2]%2)*(k//2*(-len(s)==~g[0])or k-1)))
# Original solution
from itertools import*
s,k=open(0)
k=int(k)
g=[len(list(v))for _,v in groupby(s)]
print((sum(c//2for c in g)*k-((s[0]==s[-2])*g[0]%2&g[-2]%2)*(-k//2**(len(s)-1==g[0])+1)))

# Optimized solution
from itertools import*
s,k=open(0)
k=int(k)
g=[len(list(v))for _,v in groupby(s)]
print((sum(c//2for c in g)*k-(g[0]%2*g[-2]%2*s[0]==s[-2])*(-k//2**(len(s)-1==g[0])+1)))
# Original solution
from itertools import*
s,k=open(0)
k=int(k)
g=[len(list(v))for _,v in groupby(s)]
print((sum(c//2for c in g)*k-(g[0]%2*g[-2]%2*s[0]==s[-2])*(-k//2**(len(s)-1==g[0])+1)))

# Optimized solution
from itertools import*
s,k=open(0)
k=int(k)
g=[len(list(v))for _,v in groupby(s)]
print((sum(c//2for c in g)*k-(g[0]*g[-2]%2*s[0]==s[-2])*(-k//2**(len(s)-1==g[0])+1)))
# Original solution
from itertools import*
s,k=open(0)
k=int(k)
g=[len(list(v))for _,v in groupby(s)]
print((sum(c//2for c in g)*k+((g[0]*g[-2]%2*s[0]==s[-2])*~-k>>(len(s)-1==g[0]))))

# Optimized solution
from itertools import*
s,k=open(0)
k=int(k)
g=[len(list(v))for _,v in groupby(s)]
print((sum(c//2for c in g)*k+((g[0]*g[-2]%2*s[0]==s[-2])*~-k>>(len(s)-2<g[0]))))
# Original solution
# 75

import sys
sys.setrecursionlimit(10**8)

MOD = 10**9+7
N = int(eval(input()))
g_l = [[] for i in range(N)]
check_l = [-1] * N
num_l = [0] * N
for i in range(N-1):
    ai, bi = list(map(int, input().split()))
    g_l[ai-1].append(bi-1)
    g_l[bi-1].append(ai-1)


def dfs(n):
    d = 1
    if check_l[n] > 0:
        return num_l[n]
    check_l[n] = 1
    for next_n in g_l[n]:
        d += dfs(next_n)
    num_l[n] = d
    return d


def modpow(a, n):
    # calc : (a**n)%MOD
    ret = 1
    while n > 0:
        if n & 1:
            ret = (ret * a) % MOD
        a = (a * a) % MOD
        n >>= 1
    return ret


def modinv(a):
    # calc : (a**(-1)) %MOD
    return modpow(a, MOD-2)


dfs(0)

ans = 0
# for i in range(1, N):
#     ans += (1 - (1/2)**num_l[i]) * (1 - (1/2)**(N-num_l[i]))
# ans += 1 - (1/2)**N  # 辺の期待値→頂点の期待値に変換(空集合以外は+1される)
# ans -= N/2  # 黒点の期待値を引く
for i in range(1, N):
    ans = (ans + (pow(2, num_l[i], MOD)-1) *
           (pow(2, N-num_l[i])-1) % MOD) % MOD
ans = (ans + (pow(2, N, MOD) - 1) - (N * pow(2, N-1, MOD)) % MOD) % MOD
y = ans
x = pow(2, N, MOD)

z = (y * modinv(x)) % MOD

print(z)


# Optimized solution
# 75

import sys
sys.setrecursionlimit(10**8)

MOD = 10**9+7
N = int(eval(input()))
g_l = [[] for i in range(N)]
check_l = [-1] * N
num_l = [0] * N
for i in range(N-1):
    ai, bi = list(map(int, input().split()))
    g_l[ai-1].append(bi-1)
    g_l[bi-1].append(ai-1)


def dfs(n):
    d = 1
    if check_l[n] > 0:
        return num_l[n]
    check_l[n] = 1
    for next_n in g_l[n]:
        d += dfs(next_n)
    num_l[n] = d
    return d


def modinv(a):
    # calc : (a**(-1)) %MOD
    return pow(a, MOD-2, MOD)


def solve():
    dfs(0)
    pow_l = [None]*(N+1)
    pow_l[0] = 1
    for i in range(1, N+1):
        pow_l[i] = (pow_l[i-1] * 2) % MOD

    ans = 0
    # for i in range(1, N):
    #     ans += (1 - (1/2)**num_l[i]) * (1 - (1/2)**(N-num_l[i]))
    # ans += 1 - (1/2)**N  # 辺の期待値→頂点の期待値に変換(空集合以外は+1される)
    # ans -= N/2  # 黒点の期待値を引く
    for i in range(1, N):
        ans = (ans + (pow_l[num_l[i]]-1) *
               (pow_l[N-num_l[i]]-1) % MOD) % MOD
    ans = (ans + (pow_l[N] - 1) - (N * pow_l[N-1]) % MOD) % MOD
    y = ans
    x = pow(2, N, MOD)

    z = (y * modinv(x)) % MOD

    print(z)


solve()
# Original solution
import sys
sys.setrecursionlimit(10**6)
from collections import defaultdict
mod = 10**9+7
N = int(eval(input()))
g = [[] for _ in range(N)]
d = defaultdict(lambda:-1)
p2 = [1]*(N+1)
p2[1] = pow(2,mod-2,mod)
for i in range(N):
    p2[i+1] = (p2[i]*p2[1])%mod

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

def dfs(i,j):
    if d[(i,j)]!=-1:
        return d[(i,j)]
    res = 1
    for k in g[j]:
        if k==i:
            continue
        res += dfs(j,k)
    d[(i,j)] = res
    return res

for i in range(N):
    if len(g[i])==1:
        dfs(i,g[i][0])
        break

ans = 1-p2[N]-N*p2[1]

for i in range(N):
    for j in g[i]:
        if j<i:
            continue
        n = max(d[(i,j)],d[(j,i)])
        ans += (1-p2[n])*(1-p2[N-n])
        ans %= mod

print(ans)

# Optimized solution
from collections import defaultdict,deque
mod = 10**9+7
N = int(eval(input()))
g = [[] for _ in range(N)]
d = defaultdict(lambda:-1)
p2 = [1]*(N+1)
p2[1] = pow(2,mod-2,mod)
for i in range(N):
    p2[i+1] = (p2[i]*p2[1])%mod

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

q = deque([[a,b]])
while q:
    i,j = q.pop()
    s = 1
    f = True
    for k in g[j]:
        if k == i:
            continue
        if (j,k) not in d:
            if f:
                q.append([i,j])
            q.append([j,k])
            f = False
        else:
            s += d[(j,k)]
    if f:
        d[(i,j)] = s

q = deque([[b,a]])
while q:
    i,j = q.pop()
    s = 1
    f = True
    for k in g[j]:
        if k == i:
            continue
        if (j,k) not in d:
            if f:
                q.append([i,j])
            q.append([j,k])
            f = False
        else:
            s += d[(j,k)]
    if f:
        d[(i,j)] = s

ans = 1-p2[N]-N*p2[1]

for i in range(N):
    for j in g[i]:
        if j<i:
            continue
        n = max(d[(i,j)],d[(j,i)])
        ans += (1-p2[n])*(1-p2[N-n])
        ans %= mod

print(ans)
# Original solution
# ref https://qiita.com/ZhangChaoran/items/71fab0e4b8647a93d3a0
from collections import deque
import sys
input = sys.stdin.readline

n = int(eval(input()))
g = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = list(map(int, input().split()))
    g[a].append(b)
    g[b].append(a)

mod = 10**9 + 7
par = [0] * (n + 1)
order = []
stk = deque()
stk.append(1)

while stk:
    v = stk.pop()
    order.append(v)
    for x in g[v]:
        if x == par[v]:
            continue
        par[x] = v
        stk.append(x)

rev = pow(2, mod - 2, mod)
po2_inv = [1] * (n + 1)
size = [1] * (n + 1)
for i, y in enumerate(order[::-1], 1):
    p = par[y]
    size[p] += size[y]
    po2_inv[i] = po2_inv[i - 1] * rev % mod

ans = 1
for i in size[2:]:
    ans += (1 - po2_inv[i] - po2_inv[n - i] + po2_inv[n]) % mod
ans -= po2_inv[n] + n * po2_inv[1]
ans %= mod
print(ans)


# Optimized solution
# ref https://qiita.com/ZhangChaoran/items/71fab0e4b8647a93d3a0
from collections import deque
import sys
input = sys.stdin.readline

n = int(eval(input()))
g = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = list(map(int, input().split()))
    g[a].append(b)
    g[b].append(a)

mod = 10**9 + 7
par = [0] * (n + 1)
order = []
stk = deque()
stk.append(1)

while stk:
    v = stk.pop()
    order.append(v)
    for x in g[v]:
        if x == par[v]:
            continue
        par[x] = v
        stk.append(x)

rev = (mod + 1) // 2
po2_inv = [1] * (n + 1)
size = [1] * (n + 1)
for i, y in enumerate(order[::-1], 1):
    p = par[y]
    size[p] += size[y]
    po2_inv[i] = po2_inv[i - 1] * rev % mod

ans = 1
for i in size[2:]:
    ans += (1 - po2_inv[i] - po2_inv[n - i] + po2_inv[n]) % mod
ans -= po2_inv[n] + n * po2_inv[1]
ans %= mod
print(ans)
# Original solution
import sys
from itertools import accumulate

sys.setrecursionlimit(10 ** 5)


def dfs1(v, p):
    parent[v] = p
    stc = subtree_count[v]
    cnt = 1
    for u in links[v]:
        if u == p:
            continue
        result = dfs1(u, v)
        stc[u] = result
        cnt += result
    return cnt


def dfs2(v, pc):
    # pc: vを根とした時の、parent方面の部分木のノード数
    global ans

    if len(subtree_count[v]) == 0:
        return

    p = parent[v]
    children, st_counts = list(map(list, list(zip(*list(subtree_count[v].items())))))
    children.append(p)
    st_counts.append(pc)
    cl = len(st_counts)
    ct = sum(st_counts)

    for u, stc in list(subtree_count[v].items()):
        dfs2(u, ct - stc + 1)

    if cl == 1:
        return

    prob_fwd = [0] + list(accumulate(st_counts[:-1]))
    prob_bwd = [0] + list(accumulate(st_counts[-1:0:-1]))
    prob_bwd.reverse()
    tmp = 0
    for pf, pb in zip(prob_fwd, prob_bwd):
        tmp = (tmp + d2s[pf + pb]) % MOD
    tmp = (tmp - d2s[ct] * (cl - 1)) % MOD
    ans = (ans + (1 - tmp) * d2) % MOD


n = int(eval(input()))
links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = list(map(int, line.split()))
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
root = 0
parent = [-1] * n
subtree_count = [{} for _ in range(n)]  # 根がrootの時の、vの子の各部分木のノード数
MOD = 10 ** 9 + 7
d2 = 500000004  # 2^-1 mod 10**9+7
d2s = [1]
for i in range(n):
    d2s.append(d2s[-1] * d2 % MOD)
ans = 0
dfs1(root, -1)
# print(parent)
# print(subtree_count)
dfs2(root, 0)
print(ans)


# Optimized solution
import sys

sys.setrecursionlimit(200001)


def dfs1(v, p):
    parent[v] = p
    stc = subtree_count[v]
    cnt = 1
    for u in links[v]:
        if u == p:
            continue
        result = dfs1(u, v)
        stc[u] = result
        cnt += result
    return cnt


def dfs2(v, pc):
    # pc: vを根とした時の、parent方面の部分木のノード数
    global ans

    if len(subtree_count[v]) == 0:
        return

    p = parent[v]
    children, st_counts = list(map(list, list(zip(*list(subtree_count[v].items())))))
    children.append(p)
    st_counts.append(pc)
    cl = len(st_counts)
    ct = sum(st_counts)

    for u, stc in list(subtree_count[v].items()):
        dfs2(u, ct - stc + 1)

    if cl == 1:
        return

    tmp = 0
    for stc in st_counts:
        tmp = (tmp + d2s[ct - stc]) % MOD
    tmp = (tmp - d2s[ct] * (cl - 1)) % MOD
    ans = (ans + (1 - tmp) * d2) % MOD


n = int(eval(input()))
links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = list(map(int, line.split()))
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
root = 0
parent = [-1] * n
subtree_count = [{} for _ in range(n)]  # 根がrootの時の、vの子の各部分木のノード数
MOD = 10 ** 9 + 7
d2 = 500000004  # 2^-1 mod 10**9+7
d2s = [1]
for i in range(n):
    d2s.append(d2s[-1] * d2 % MOD)
ans = 0
dfs1(root, -1)
# print(parent)
# print(subtree_count)
dfs2(root, 0)
print(ans)
# Original solution
p = 1000000007
N = int(eval(input()))
T = [[] for _ in range(N)]
for _ in range(N - 1):
  (a, b) = (int(x) - 1 for x in input().split())
  T[a].append(b)
  T[b].append(a)
P = [-1] * N
P[0] = 0
Q = [0]
for i in range(N):
  q = Q[i]
  for adj in T[q]:
    if 0 <= P[adj]:
      continue
    P[adj] = q
    Q.append(adj)
ST = [[] for _ in range(N)]
for q in Q[N - 1:0:-1]:
  s = sum(ST[q]) + 1
  ST[P[q]].append(s)
  ST[q].append(N - s)
B = [pow(1 << i, p - 2, p) for i in range(N)]
H = [0] * N
ans = 0
for S in ST:
  ans += B[1] * ((1 - B[-1] - sum([(B[N - 1 - s] * (1 - B[s])) % p for s in S])) % p)
  ans %= p
print(ans)

# Optimized solution
p = 1000000007
N = int(eval(input()))
T = [[] for _ in range(N)]
for _ in range(N - 1):
  (a, b) = (int(x) - 1 for x in input().split())
  T[a].append(b)
  T[b].append(a)
P = [-1] * N
P[0] = 0
Q = [0]
for i in range(N):
  q = Q[i]
  for adj in T[q]:
    if 0 <= P[adj]:
      continue
    P[adj] = q
    Q.append(adj)
ST = [[] for _ in range(N)]
for q in Q[N - 1:0:-1]:
  s = sum(ST[q]) + 1
  ST[P[q]].append(s)
  ST[q].append(N - s)
B = [1] * N
B[-1] = pow(1 << (N - 1), p - 2, p)
for i in range(N - 1, 0, -1):
  B[i - 1] = B[i] * 2 % p
H = [0] * N
ans = 0
for S in ST:
  ans += B[1] * ((1 - B[-1] - sum([(B[N - 1 - s] * (1 - B[s])) % p for s in S])) % p)
  ans %= p
print(ans)
# Original solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

N = int(eval(input()))
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  A, B = list(map(int, input().split()))
  vec[A-1].append(B-1)
  vec[B-1].append(A-1)

sub_size = [[] for _ in range(N)]

def dfs(cur, pre) :
  s = 0
  for nex in vec[cur] :
    if nex == pre :
      continue
    t = dfs(nex, cur)
    s += t
    sub_size[cur].append(t)
  if s != N - 1 :
    sub_size[cur].append(N - 1 - s)

  return s + 1

dfs(0, -1)

fac = [1]
inv = [1]
div = pow(2, mod - 2, mod)
for _ in range(N) :
  fac.append(fac[-1] * 2 % mod)
  inv.append(inv[-1] * div % mod)

ret = 0
for i in range(N) :
  if len(sub_size[i]) < 2 :
    continue

  a, b = 1, 1
  for ss in sub_size[i] :
    a *= inv[ss]
    b += fac[ss] - 1
    a %= mod
    b %= mod
  ret += (1 - a * b) % mod
  ret %= mod

ret = ret * div % mod

print(ret)

# Optimized solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

N = int(eval(input()))
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  A, B = list(map(int, input().split()))
  vec[A-1].append(B-1)
  vec[B-1].append(A-1)

own_size = [0] * N
sub_size = [[] for _ in range(N)]

# pythonのdfs重すぎて自分でstack書かないと通らない。
# く〜〜つらいとこね、これ！！！！
stack = [(0, -1)]
for i in range(N) :
  cur, pre = stack[i]
  for nex in vec[cur] :
    if nex != pre :
      stack.append((nex, cur))

while stack :
  cur, pre = stack.pop()
  if pre != -1 :
    sub_size[pre].append(own_size[cur] + 1)
    own_size[pre] += own_size[cur] + 1
  if own_size[cur] != N - 1 :
    sub_size[cur].append(N - 1 - own_size[cur])

fac = [1]
inv = [1]
div = pow(2, mod - 2, mod)
for _ in range(N) :
  fac.append(fac[-1] * 2 % mod)
  inv.append(inv[-1] * div % mod)

ret = 0
for i in range(N) :
  if len(sub_size[i]) < 2 :
    continue

  a, b = 1, 1
  for ss in sub_size[i] :
    a *= inv[ss]
    b += fac[ss] - 1
    a %= mod
    b %= mod
  ret += (1 - a * b) % mod
  ret %= mod

ret = ret * div % mod

print(ret)
# Original solution
import sys
sys.setrecursionlimit(5+10**5)
mod=10**9+7
N=int(eval(input()))
G=[[] for i in range(N)]
for i in range(N-1):
    A,B=list(map(int,input().split()))
    G[A-1].append(B-1)
    G[B-1].append(A-1)
Child=[[] for i in range(N)]

#print(Child)
#print(Parents)
#print(G)
reached=[0 for i in range(N)]
Childnum=[0 for i in range(N)]
def dp(i):
    if reached[i]==1:
        return Childnum[i]
    reached[i]=1
    res=0
    for j in G[i]:
        if reached[j]==1:
            continue
        Child[i].append(j)
        res+=dp(j)+1
    Childnum[i]=res
    return res
dp(0)
#print(Child)
#print(Childnum)
def inv(x):
    return pow(x,mod-2,mod)
inv2=[inv(pow(2,i,mod)) for i in range(N+1)]
ans=(N*(1-inv(pow(2,N-1,mod))))%mod
for r in range(N):
    tmp=0
    for p in Child[r]:
        ai=Childnum[p]+1
        tmp+=ai
        k1=(1-inv2[ai])%mod
        k2=inv2[N-1-ai]
        #print(r,p,(k1*k2)%mod)
        ans-=(k1*k2)%mod
        ans%=mod
    ai=N-1-tmp
    k1=(1-inv2[ai])%mod
    k2=inv2[N-1-ai]
    ans-=(k1*k2)%mod
    #print(r,-1,(k1*k2)%mod)
    ans%=mod
print(((ans*inv(2))%mod))


# Optimized solution
import sys
sys.setrecursionlimit(2*10**5)
mod=10**9+7
N=int(eval(input()))
G=[[] for i in range(N)]
for i in range(N-1):
    A,B=list(map(int,input().split()))
    G[A-1].append(B-1)
    G[B-1].append(A-1)
Child=[[] for i in range(N)]

#print(Child)
#print(Parents)
#print(G)
reached=[0 for i in range(N)]
Childnum=[0 for i in range(N)]
def dp(i):
    if reached[i]==1:
        return Childnum[i]
    reached[i]=1
    res=0
    for j in G[i]:
        if reached[j]==1:
            continue
        Child[i].append(j)
        res+=dp(j)+1
    Childnum[i]=res
    return res
dp(0)
#print(Child)
#print(Childnum)
def inv(x):
    return pow(x,mod-2,mod)
inv2=[inv(pow(2,i,mod)) for i in range(N+1)]
ans=(N*(1-inv(pow(2,N-1,mod))))%mod
for r in range(N):
    tmp=0
    for p in Child[r]:
        ai=Childnum[p]+1
        tmp+=ai
        k1=(1-inv2[ai])%mod
        k2=inv2[N-1-ai]
        #print(r,p,(k1*k2)%mod)
        ans-=(k1*k2)%mod
        ans%=mod
    ai=N-1-tmp
    k1=(1-inv2[ai])%mod
    k2=inv2[N-1-ai]
    ans-=(k1*k2)%mod
    #print(r,-1,(k1*k2)%mod)
    ans%=mod
print(((ans*inv(2))%mod))
# Original solution
import sys
sys.setrecursionlimit(2 * 10 ** 5 + 10)

mod = 10 ** 9 + 7

N, *AB = list(map(int, open(0).read().split()))

E = [[] for _ in range(N)]
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a - 1].append((b - 1, i))
    E[b - 1].append((a - 1, i))

X = [0] * N

def dfs(u, p):
    res = 1
    for v, c in E[u]:
        if p != c:
            res += dfs(v, c)
    X[p] = res
    return res

dfs(0, -1)

I = [1] * (N + 1)
inv = pow(2, mod - 2, mod)
for i in range(N):
    I[i + 1] = I[i] * inv % mod

ans = - inv * N - I[N] + 1
for e in range(N - 1):
    ans += (1 - I[X[e]]) * (1 - I[N - X[e]])
    ans %= mod

print(ans)

# Optimized solution
import sys
sys.setrecursionlimit(2 * 10 ** 5 + 10)

mod = 10 ** 9 + 7

N, *AB = list(map(int, open(0).read().split()))

E = [[] for _ in range(N)]
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a - 1].append((b - 1, i))
    E[b - 1].append((a - 1, i))

X = [0] * N

def dfs(u, p):
    res = 1
    for v, c in E[u]:
        if p != c:
            res += dfs(v, c)
    X[p] = res
    return res

dfs(0, -1)

I = [1] * (N + 1)
inv = pow(2, mod - 2, mod)
for i in range(N):
    I[i + 1] = I[i] * inv % mod

ans = - inv * N - I[N] + 1 + sum((1 - I[x]) * (1 - I[N - x]) for x in X)
ans %= mod

print(ans)
# Original solution
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

def DFS(G, W, Wlist, visit, node):
	for i in G.graph[node]:
		if visit[i] != "Yes":
			visit[i] = "Yes"
			DFS(G, W, Wlist, visit, i)
			W[node] += W[i]
			Wlist[node].append(W[i])

#処理内容
def main():
	#入力
	N = int(eval(input()))
	G = Graph()
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)

	#DFS
	W = [1] * N
	Wlist = [[0] for i in range(N)]
	visit = ["No"] * N
	visit[0] = "Yes"
	DFS(G, W, Wlist, visit, 0)
	# print(W)
	# print(Wlist)
	for i in range(N):
		Wlist[i].append(N - 1 - sum(Wlist[i]))

	# print(Wlist)
	ans_up = 0
	pow2 = pow(2, N - 1, con)
	for i in range(N):
		ans_up += pow2 - 1
		for j in Wlist[i]:
			ans_up -= pow(2, j, con) - 1

	# print(ans_up)

	ans = ans_up * pow(pow2 * 2, con - 2, con)
	print((ans % con))

if __name__ == '__main__':
	main()

# Optimized solution
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

def DFS(G, W, Wlist, visit, node):
	for i in G.graph[node]:
		if visit[i] != "Yes":
			visit[i] = "Yes"
			DFS(G, W, Wlist, visit, i)
			W[node] += W[i]
			Wlist[node].append(W[i])

#処理内容
def main():
	#入力
	N = int(eval(input()))
	G = Graph()
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)

	#DFS
	W = [1] * N
	Wlist = [[0] for i in range(N)]
	visit = ["No"] * N
	visit[0] = "Yes"
	DFS(G, W, Wlist, visit, 0)
	# print(W)
	# print(Wlist)
	for i in range(N):
		Wlist[i].append(N - W[i])

	# print(Wlist)
	ans_up = 0
	pow2 = pow(2, N - 1, con)
	for i in range(N):
		ans_up += pow2 - 1
		for j in Wlist[i]:
			ans_up -= pow(2, j, con) - 1
			ans_up %= con

	# print(ans_up)

	ans = ans_up * pow(pow2 * 2, con - 2, con)
	print((ans % con))

if __name__ == '__main__':
	main()