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

class DLL:
    class Node:
        def __init__(self, x, y, z):
            self.v = x
            self.prv = y
            self.nxt = z

    def __init__(self):
        init = DLL.Node(None, None, None)
        init.prv = init
        init.nxt = init
        self.size = 0
        self.init = init

    def insert(self, x):
        i = self.init
        j = i.nxt
        k = DLL.Node(x, i, j)
        i.nxt = k
        j.prv = k
        self.size += 1

    def deleteFirst(self):
        #if self.size != 0:
        i = self.init
        k = i.nxt
        j = k.nxt
        i.nxt = j
        j.prv = i
        self.size -= 1

    def deleteLast(self):
        #if self.size != 0:
        i = self.init
        k = i.prv
        j = k.prv
        i.prv = j
        j.nxt = i
        self.size -= 1

    def delete(self, x):
        #if self.size != 0:
        i = self.init
        k = i.nxt
        while 1:
            if k.v == x:
                i = k.prv
                j = k.nxt
                i.nxt = j
                j.prv = i
                self.size -= 1
                break
            else:
                if k.nxt == i:
                    break
                else:
                    k = k.nxt

    def prt(self):
        f = self.init
        s = f.nxt
        l = f.prv
        while 1:
            if s != l:
                print(s.v, end=' ')
                s = s.nxt
            else:
                print(l.v)
                break

n = int(input())
L = DLL()

for i in range(n):
    com = input()
    if com == "deleteFirst":
        L.deleteFirst()
    elif com == "deleteLast":
        L.deleteLast()
    else:
        C = com.split()
        if C[0] == "insert":
            L.insert(int(C[1]))
        elif C[0] == "delete":
            L.delete(int(C[1]))
    #L.prt()
    
L.prt()



### FIXED CODE ###

from collections import deque

n = int(input())
L = deque()

for i in range(n):
    com = input()
    if com[0] == 'i':
        C = com.split()
        L.appendleft(int(C[1]))
    else:
        if com[6] == 'F':
            L.popleft()
        elif com[6] == 'L':
            L.pop()
        else:
            C = com.split()
            x = int(C[1])
            try:
                L.remove(x)
            except:
                pass

print(*L)
### BUGGY CODE ###

s = input()
k = int(input())
 
sl = [s]
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        ss = s[i:j]
        sl.append(ss)
sl = sorted(list(set(sl)))
print(sl[k-1])

### FIXED CODE ###

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

sl = [s]
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        if j - i > k:
            break
        ss = s[i:j]
        sl.append(ss)
sl = sorted(list(set(sl)))
print(sl[k-1])
### BUGGY CODE ###

from operator import mul
from functools import reduce


def ccnt(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


k = int(input())
s = input()
length = len(s)
MOD = 10**9 + 7

ans = 0

for i in range(length, length + k + 1):
    ans += ccnt(i - 1, length - 1) * pow(25, i - length, MOD) * pow(26, length + k - i, MOD) % MOD

print(ans % MOD)

### FIXED CODE ###

def solve(k, length, MOD, div, dp):
    for i in range(1, k + 1):
        dp[0] = dp[0] * 25 * div * (length + i - 1) * pow(i, -1, MOD) % MOD
        dp[1] = (dp[1] + dp[0]) % MOD

    return(dp[1])


k = int(input())
s = input()
length = len(s)
MOD = 10**9 + 7
div = pow(26, -1, MOD)

dp = [pow(26, k, MOD)] * 2

print(solve(k, length, MOD, div, dp))
### BUGGY CODE ###

def f(a: int, b: int) -> int:
  return a ** 5 - b ** 5

x = int(input())
factor = []
fact = 1
while fact * fact < x:
  if x % fact == 0:
    factor.append(fact)
    factor.append(x // fact)
  fact += 1
if fact * fact == x:
  factor.append(fact)
for d in factor:
  if x // d % 5 > 1:
    continue
  a = d // 2
  while f(a, a - d) < x:
    a *= 2
  if f(a, a - d) == x:
    print(a, a - d)
    break
  upper = a
  lower = a // 2
  while upper - lower > 1:
    a = (upper + lower) // 2
    value = f(a, a - d)
    if value < x:
      lower = a
    elif value > x:
      upper = a
    else:
      print(a, a - d)
      break
  else:
    if f(lower, lower - d) == x:
      print(lower, lower - d)
    continue
  break

### FIXED CODE ###

x = int(input())
for a in range(-200, 200):
  for b in range(-200, 200):
    if a ** 5 - b ** 5 == x:
      print(a, b)
      break
  else:
    continue
  break
### BUGGY CODE ###

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

I = [[] for _ in range(N)] #各種類の玉がどこにあるか
for i in range(N):
  I[C[i]-1].append(i)
  
BIT = [0 for _ in range(N+1)]
# Binary Indexed Tree 
# https://juppy.hatenablog.com/entry/2018/11/17/%E8%9F%BB%E6%9C%AC_python_Binary_Indexed_Tree_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
def BIT_query(idx): #idxまでの和(1からスタート)
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx) #一番下の位を減らす（例：13=1011 → 1010 → 1000） 
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x): #idxをx増やした時
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx) #一番下の位を繰り上げる（例：13=1011 → 1100 → 10000 ※N=16のとき） 
    return

loc = [0 for _ in range(N)]#各種類の玉のうちの最右端の所在地
for c in range(N):
  if I[c]:
    i = I[c][-1]
    BIT_update(i+1, 1) #各種類の玉について、最右端の所在地に1記入
    loc[i] = c+1 #各種類の玉について、最右端の所在地に玉の種類を記入
    
S = [[list(map(int, input().split())), i] for i in range(Q)] #クエリ
S.sort(key = lambda a: a[0][1]) #区間の右端でソート
#print(S)
#print(I)

ans = [0 for _ in range(Q)]
for j in range(N-1,-1,-1):
  t = BIT_query(j+1)
  while S and S[-1][0][1] == j+1:#クエリへの返答
    s = S.pop()
    ans[s[1]] = t - BIT_query(s[0][0]-1)
  
  if not S:
    break
    
  if loc[j] > 0: #最右端の玉である場合
    c = loc[j]-1
    I[c].pop()
    if I[c]:
      BIT_update(I[c][-1]+1, 1)
      loc[I[c][-1]] = c+1
       
for a in ans:
  print(a)


### FIXED CODE ###

from sys import stdin
#import numpy as np

readline = stdin.readline

N, Q = map(int, readline().split()) 
C = list(map(int, readline().split())) 
S = [list(map(int, readline().split())) for _ in range(Q)] 
#print(S)
def main(N, Q, C, S):    
  # Binary Indexed Tree 
  # https://juppy.hatenablog.com/entry/2018/11/17/%E8%9F%BB%E6%9C%AC_python_Binary_Indexed_Tree_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
  b = [0 for _ in range(N+1)]
  def BIT_query(idx): #idxまでの和(1からスタート)
    res_sum = 0
    while idx > 0:
      res_sum += b[idx]
      idx -= idx&(-idx) #一番下の位を減らす（例：13=1011 → 1010 → 1000） 
    return res_sum
  def BIT_update(idx,x): #idxをx増やした時
    while idx <= N:
      b[idx] += x
      idx += idx&(-idx) #一番下の位を繰り上げる（例：13=1011 → 1100 → 10000 ※N=16のとき） 
    return

  loc = [0 for _ in range(N)] #各種類の玉のうちの最右端の所在地
  S = [(S[i], i) for i in range(Q)] #クエリ
  S.sort(key = lambda s: s[0][1]) #区間の右端でソート
  #S = np.array(S, dtype = np.int64)
  #print(S)
  ans = [0 for _ in range(Q)]
  k = 0
  for j in range(N):
    if loc[C[j]-1] > 0: #玉の更新
      BIT_update(loc[C[j]-1], -1)
    loc[C[j]-1] = j+1
    BIT_update(j+1, 1)  
    
    if S[k][0][1] == j+1:
      t = BIT_query(j+1)
    while k < len(S) and S[k][0][1] == j+1: #クエリへの返答
      ans[S[k][1]] = t - BIT_query(S[k][0][0]-1)
      k += 1
    if k == len(S):
      break
  return ans

ans = main(N, Q, C, S)
print(*ans, sep='\n')
### BUGGY CODE ###

a,b,k=map(int, input().split())
l=[int(i) for i in range(a,b+1)]

l2=set(l[:k]+l[-k:])

print(" ".join(map(str, sorted(l2)) ))

### FIXED CODE ###

a,b,k=map(int,input().split())
ans=[]
for i in range(a,min(a+k,b+1)):
    ans.append(i)
for j in range(b,max(b-k,a-1),-1):
    if j not in ans:
        ans.append(j)
ans.sort()
for k in range(len(ans)):
  print(ans[k])
### BUGGY CODE ###

n, k = map(int, input().split())
arr = list(map(int, input().split()))
num_arr = [1]*n
length_arr = [l for l in arr]

for i in range(k):
  max_idx = length_arr.index(max(length_arr))
  tmp = num_arr[max_idx] + 1
  num_arr[max_idx] = tmp
  length_arr[max_idx] = arr[max_idx] / tmp

result_int = max(length_arr) - 0.0001
print(int(result_int//1 + 1))


  

### FIXED CODE ###

import math
n, k = map(int, input().split())
arr = list(map(int, input().split()))

max_length = max(arr)
low = 1
high = max_length - 1

while low <= high:
  mid = (low + high) //2
  cnt = 0
  for i in range(n):
    cnt += math.ceil(arr[i]/mid) - 1
  if cnt > k:
    low = mid + 1
  else:
    high = mid -1
    max_length = mid

print(max_length)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)


def dfs(v, par):
    for nv in tree[v]:
        if nv == par:
            continue
        add[nv] += add[v]
        dfs(nv, v)


n, q = map(int, input().split())
tree = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree[b].append(a)
    tree[a].append(b)
add = [0] * n
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    add[p] += x
dfs(0, -1)
print(*add)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline


def dfs(v, par):
    for nv in tree[v]:
        if nv == par:
            continue
        add[nv] += add[v]
        dfs(nv, v)


n, q = map(int, input().split())
tree = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree[b].append(a)
    tree[a].append(b)
add = [0] * n
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    add[p] += x
dfs(0, -1)
print(*add)
### BUGGY CODE ###

X=int(input())

Xkon=X**0.2
if(Xkon==int(Xkon)):
    print(str(0)+" "+str(int(-Xkon)))
    #break
else:
    m=-(10**3)
    while m<0:
        A=X+(m**5)
        check=(A**0.2)
        # print(type(check))
        if(type(check)!=complex):
            if(check==int(check)):
                AnsA=-check
                AnsB=-m
                print(str(int(AnsB))+" "+str(int(AnsA)))
                break
            else:
                pass
        else:
            m=m+1
    n=1
    while n<10**3:
        A=X+(n**5)
        check=(A**0.2)
        if(check==int(check)):
            AnsA=check
            AnsB=n
            print(str(int(AnsB)+" "+str(int(-AnsA))))
            break
        else:
            n=n+1


### FIXED CODE ###

X=int(input())

for A in range(-1000,1000):
    for B in range (-1000,1000):
        if(A**5-B**5==X):
            print(A,B)
            break
    else:
        continue
    break
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,k,q=map(int,input().split())
A=[int(input()) for _ in range(q)]

minus=[]
for i in range(1,n+1):
  minus.append(A.count(i))
for i in range(n):
  if k-(q-minus[i])<=0:
    print('No')
  else:
    print('Yes')

### FIXED CODE ###

import sys
import itertools
input = sys.stdin.readline
n,k,q=map(int,input().split())
A=[int(input()) for _ in range(q)]

ans=[k]*n
for i in range(q):
  ans[A[i]-1]+=1
for i in range(n):
  if ans[i]-q>0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

from heapq import heappop, heappush


def main():
    N, M, S = map(int, input().split())
    adj = [{} for _ in range(N)]
    amax = 0
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        adj[u-1][v-1] = (a, b)
        adj[v-1][u-1] = (a, b)
        amax = max(amax, a)
    C = [0] * N
    D = [0] * N
    for i in range(N):
        C[i], D[i] = map(int, input().split())
    MAX = amax * N
    dp = [[float("inf")] * (MAX+1) for _ in range(N)]
    q = [(0, min(S, MAX), 0)]
    ans = [None] * N
    while len(q) and None in ans:
        time, coin, cur = heappop(q)
        if dp[cur][coin] <= time:
            continue
        if ans[cur] is None:
            ans[cur] = time
        dp[cur][coin] = time
        if coin < MAX:
            heappush(q, (time + D[cur], min(coin + C[cur], MAX), cur))
        for nxt in adj[cur]:
            dcost, dtime = adj[cur][nxt]
            if dcost <= coin:
                heappush(q, (time + dtime, coin - dcost, nxt))
    for i in range(1, N):
        print(ans[i])


if __name__ == "__main__":
    main()


### FIXED CODE ###

from heapq import heappop, heappush


def main():
    N, M, S = map(int, input().split())
    adj = [{} for _ in range(N)]
    amax = 0
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        adj[u-1][v-1] = (a, b)
        adj[v-1][u-1] = (a, b)
        amax = max(amax, a)
    C = [0] * N
    D = [0] * N
    for i in range(N):
        C[i], D[i] = map(int, input().split())
    MAX = amax * N
    dp = [[float("inf")] * (MAX+1) for _ in range(N)]
    q = [[0, min(S, MAX), 0, -1]]
    ans = [None] * N
    remain = N
    while len(q) and remain:
        time, coin, cur, prev = heappop(q)
        if dp[cur][coin] <= time:
            continue
        if ans[cur] is None:
            ans[cur] = time
            remain -= 1
        dp[cur][coin] = time
        if coin < MAX:
            heappush(q, [time + D[cur], min(coin + C[cur], MAX), cur, cur])
        for nxt in adj[cur]:
            dcost, dtime = adj[cur][nxt]
            if nxt != prev and dcost <= coin:
                heappush(q, [time + dtime, coin - dcost, nxt, cur])
    for i in range(1, N):
        print(ans[i])


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

from sys import exit

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

S = input()

AC = []
for i in range(len(S) - 1):
    if S[i] == 'A':
        if S[i + 1] == 'C':
            AC.append(i)

ans = []

for i in range(Q):
    li, ri = map(int, input().split())
    count = 0
    if li - ri > len(S) / 2:
        for ac in AC:
            if ac < li - 1:
                count += 1
            else:
                break
        for ac in reversed(AC):
            if ri - 1 < ac + 1:
                count += 1
            else:
                break
        ans.append(len(AC) - count)
    else:
        for i in range(li - 1, ri - 1):
            if i in AC:
                count += 1
        ans.append(count)

for a in ans:
    print(a)


### FIXED CODE ###

from sys import exit

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

S = input()

AC = [0] * N

c = 0

for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        c += 1
    AC[i + 1] = c

for _ in range(Q):
    li, ri = map(int, input().split())
    print(AC[ri - 1] - AC[li - 1])
### BUGGY CODE ###

import math
from functools import reduce


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


n = int(input())
num = 0

for a in range(1, n+1):
    for b in range(1, n+1):
        for c in range(1, n+1):
            num += gcd(a, b, c)

print(num)


### FIXED CODE ###

import math
from functools import reduce


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


n = int(input())
num = 0

for a in range(1, n+1):
    for b in range(1, n+1):
        for c in range(1, n+1):
            num += gcd(a, b, c)

print(num)
### BUGGY CODE ###

N = int(input())
S = input()
X = ["{:03d}".format(i) for i in range(1000)]
# print(X)
ans = 0
for x in X:
    now = 0
    for s in S:
        if s == x[now]:
            now += 1
        if now == 3:
            ans += 1
            break
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
#0なし
numlist = [""]
dp = [False] * 1000
for s in S:
    tmp = []
    for n in numlist:
        if len(n+s) == 3:
            dp[int(n+s)] = True
        if len(n+s) < 3:
            tmp.append(n+s)
    numlist.extend(tmp)
    numlist = list(set(numlist))
print(sum(dp))
### BUGGY CODE ###

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

m = [tuple(sorted(map(int, input().split()))) for _ in range(m) ]

for i in range(2, n+1):
  route1 = (1, i)
  route2 = (i, n)
  if route1 in m and route2 in m:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")
    

### FIXED CODE ###

N,M=map(int,input().split())
sa=set()
sb=set()
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
      sb.add(b)
    if b==N:
      sa.add(a)
print("IMPOSSIBLE" if len(sa&sb)==0 else "POSSIBLE")
### BUGGY CODE ###

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

data = set()
for i in range(len(s)):
    for j in range(i, len(s)):
        data.add(s[i: j + 1])

data = sorted(data)
print(data[k - 1])

### FIXED CODE ###

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

data = set()
for i in range(len(s)):
    for j in range(i, i + k):
        data.add(s[i: j + 1])
data = sorted(data)
print(data[k - 1])
### BUGGY CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n, k, q = map(int, args[0].split())
    A = list(map(int, args[1:]))
    ret = ''
    p = 0
    for a in sorted(set(A)):
        ret += ('Yes\n' if 0 < k-q else 'No\n')*(a-p-1)
        ret += ('Yes' if 0 < k - (q - A.count(a)) else 'No') + '\n'
        p = a

    ret += ('Yes\n' if 0 < k-q else 'No\n')*(n-p)
    return ret.rstrip('\n')


if __name__ == "__main__":
    nkq = input()
    _, _, q = map(int, nkq.split())
    print(solve(*([nkq]+[input() for _ in range(q)])))


### FIXED CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n, k, q = map(int, args[0].split())
    A = sorted(map(int, args[1:]))
    S = [k-q for _ in range(n)]
    ret = ''

    for a in A:
        S[a-1] += 1

    for s in S:
        ret += ('Yes' if 0 < s else 'No') + '\n'

    return ret.rstrip('\n')


if __name__ == "__main__":
    nkq = input()
    _, _, q = map(int, nkq.split())
    print(solve(*([nkq]+[input() for _ in range(q)])))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, A: "List[List[int]]"):
    es = [
        (A[i][j], i, j)
        for i in range(N)
        for j in range(i)
    ]
    es.sort(reverse=True)
    ans = 0
    for d, i, j in es:
        for k in range(N):
            if k == i or k == j:
                continue
            nd = A[i][k] + A[k][j]
            if nd < d:
                print(-1)
                return
            if nd == d:
                break
        else:
            ans += d
    print(ans)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N)] for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, A: "List[List[int]]"):
    es = [
        (A[i][j], i, j)
        for i in range(N)
        for j in range(i)
    ]
    es.sort(reverse=True)
    ans = 0
    for d, i, j in es:
        for k in range(N):
            if k == i or k == j:
                continue
            nd = A[i][k] + A[k][j]
            if nd < d:
                print(-1)
                return
            if nd == d:
                break
        else:
            ans += d
    print(ans)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N)] for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)


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

import numpy as np

N = int(input())
A = [0]*N
X = np.zeros([N,N],dtype=int)
Y = np.zeros([N,N],dtype=int)

for n in range(N):
    A[n] = int(input())
    for a in range(A[n]):
        X[n][a], Y[n][a] = list(map(int,input().split()))

ans = 0

for bits in range( 1, 1<<N ):
    ok = True
    for i in range( 0, N ):
        if not ( bits & (1 << i) ):
            continue
        for j in range( 0, A[i] ):
            if (( bits >> (X[i][j]-1) ) & 1) ^ Y[i][j]:
                ok = False
    if ok:
        ans = max( ans, (str(bin(bits))[2:]).count('1'))
        
print(ans)

### FIXED CODE ###

import numpy as np

N = int(input())
A = [0]*N
X = np.zeros([N,N],dtype=int)
Y = np.zeros([N,N],dtype=int)

for n in range(N):
    A[n] = int(input())
    for a in range(A[n]):
        X[n][a], Y[n][a] = list(map(int,input().split()))

ans = 0

for bits in range( 1, 1<<N ):
    ok = True
    for i in range( 0, N ):
        if not ok:
            break
        if not ( bits & (1 << i) ):
            continue
        for j in range( 0, A[i] ):
            if (( bits >> (X[i][j]-1) ) & 1) ^ Y[i][j]:
                ok = False
                break
    if ok:
        ans = max( ans, (str(bin(bits))[2:]).count('1'))
        
print(ans)
### BUGGY CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import Counter
def resolve():
    S = [s for s in sr()]
    N = len(S)
    a = [0]*(N+1)
    t = ''
    for i in range(N):
        t = S.pop()+t
        a[i] = int(t)%2019
    A = Counter(a)
    ans = 0
    for n in A.values():
        ans += n*(n-1)//2
    print(ans)
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    S = sr()
    N = len(S)
    a = [0]*2019
    a[0] += 1
    t = 0
    r = 1
    for s in reversed(S):
        t += int(s)*r
        t %= 2019
        r *= 10
        r %= 2019
        a[t] += 1
    ans = 0
    for i in range(2019):
        ans += a[i]*(a[i]-1)//2
    print(ans)
resolve()
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7

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

# 頂点iから伸びてる枝それぞれのサイズ
memo = [[] for _ in range(N + 1)]


def dfs(s, p=-1):
    sub_tree = []
    res = 1
    for t in edge[s]:
        if t == p:
            continue
        size = dfs(t, s)
        sub_tree.append(size)
        res += size
    if N != res:
        sub_tree.append(N - res)
    memo[s].extend(sub_tree)
    return res


dfs(1)


cnt = 0
for lis in memo[1:]:
    if len(lis) == 1:
        continue
    # 頂点iが穴あきとならない->頂点から伸びてるやつ1つだけ黒の場合がダメ
    tmp = pow(2, N - 1, mod) - 1  # ぜんぶ白の場合を引いとく
    for x in lis:
        black = pow(2, x, mod) - 1
        tmp = (tmp - black + mod) % mod
    cnt = (cnt + tmp) % mod

div = pow(2, N, mod)
ans = cnt * pow(div, mod - 2, mod) % mod
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7

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

# 頂点iから伸びてる枝それぞれのサイズ
ans = 0
pow2 = [1] * (N + 1)
for i in range(1, N + 1):
    pow2[i] = pow2[i - 1] * 2 % mod


def dfs(s, p=-1):
    global ans
    res = 1
    tmp = pow2[N-1] - 1
    for t in edge[s]:
        if t == p:
            continue
        size = dfs(t, s)
        res += size
        tmp = (tmp - pow2[size] + 1 + mod) % mod
    if N != res:
        tmp = (tmp - pow2[N-res] + 1 + mod) % mod
    ans = (ans + tmp) % mod
    return res


dfs(1)
div = pow2[N]
print(ans*pow(div, mod-2, mod) % mod)