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

def solve():
    import sys
    n, m, *LR = map(int, sys.stdin.read().split())
    L = LR[::2]
    R = LR[1::2]
    res = set(range(1, n + 1))
    for l, r in zip(L, R):
        x = set(range(l, r + 1))
        res &= x
    print(len(res))


solve()


### FIXED CODE ###

def solve():
    import sys
    n, m, *LR = map(int, sys.stdin.read().split())
    L = LR[::2]
    R = LR[1::2]
    l = max(L)
    r = min(R)
    print(max(0, r - l + 1))


solve()
### BUGGY CODE ###

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

a_max = max(A)
a_min = min(A)
dummy = -float("inf")

for x in range(a_min-1, a_max+1+1):
    cnt = 0
    for i in range(len(A)):
        if A[i] -1 <= x and A[i] + 1 >= x:
            cnt += 1
            if dummy < cnt:
                dummy = cnt
print(dummy)


### FIXED CODE ###

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

a_max = max(A)
a_min = min(A)

cnt_dict = {}
for i in range(a_min-1, a_max+2):
    cnt_dict[i] = 0
for i in range(len(A)):
    cnt_dict[A[i]-1] += 1
    cnt_dict[A[i]] += 1
    cnt_dict[A[i]+1] += 1

print(max(cnt_dict.items(), key = lambda x: x[1])[1])
### BUGGY CODE ###

#
# author Sidratul
#

if __name__ == '__main__':
    n = input()
    a = list(map(int, input().split(' ')))
    s = 1
    for i in a:
        s = s*i
    if s > 10**18:
        print(-1)
    else:
        print(s)

### FIXED CODE ###

#
# author Sidratul
#

from math import prod

if __name__ == '__main__':
    n = input()
    a = list(map(int, input().split(' ')))
    s = 1
    a.sort()
    x = True
    for i in range(len(a)):
        s = s * a[i]
        if s > 10**18:
            print(-1)
            x = False
            break
    if x:
        print(s)
### BUGGY CODE ###

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

def combi(n):
    return n*(n-1)//2

count_all = 0
count_cut = 0


for i in range(n):
    count = a.count(i+1)
    count_all += combi(count)
    
for k in range(n):
    #aのk番目の要素と同じ要素の数を(k番目の要素も含めて)出し、1を引く
    count = a.count(a[k]) - 1
    ans = count_all - count
    print(ans)


### FIXED CODE ###

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

num_list=[0]*n
for i in range(n):
    num_list[a[i]-1]+=1

sm_all=0
for i in range(n):
    k=num_list[i]
    sm_all+=(k*(k-1))//2

for i in range(n):
    print(sm_all-(num_list[a[i]-1]-1))
### BUGGY CODE ###

import collections
N = int(input())
S = [input() for _ in range(N)]

c = collections.Counter(S)

ans = sorted([i[0] for i in c.items() if i[1] == c.most_common()[0][1]])
  
[print(a) for a in ans]


### FIXED CODE ###

import collections
N = int(input())
S = [input() for _ in range(N)]

if len(S) == len(set(S)):
  ans = S
else:
  ans = []
  c = collections.Counter(S)
  c_common = c.most_common()
  max_vote = c_common[0][1]
  for k in range(len(set(S))):
    if c_common[k][1]== max_vote:
      ans.append(c_common[k][0])
    else:
      break
[print(a) for a in sorted(ans)]
### BUGGY CODE ###

n,k = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)

def isOk(x):
    cost = 0
    for i in range(n):
        eatable = x//F[i]
        if eatable >= A[i]:
            continue
        cost += A[i] - eatable
    if cost <= k:
        return True
    return False

left = 0
# right = 1e12
right = A[-1] * F[0]
while left+1 < right:
    # mid = int(left + (right-left)//2)
    mid = (left+right)//2
    if isOk(mid):
        right = mid
    else:
        left = mid
if sum(A) <= k:
    right = 0
print(right)

### FIXED CODE ###

n,k = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)

def isOk(x):
    cost = 0
    for a, f in zip(A,F):
        eatable = x//f
        if eatable >= a:
            continue
        cost += a - eatable
    if cost <= k:
        return True
    return False

left = -1
right = A[-1] * F[0]
while left+1 < right:
    # mid = int(left + (right-left)//2)
    mid = (left+right)//2
    if isOk(mid):
        right = mid
    else:
        left = mid
print(right)
### BUGGY CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


MOD = 998244353


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    height = [[0] * W for _ in range(H)]
    width = [[0] * W for _ in range(H)]

    for h in range(H):
        cnt = 0
        for w in range(W):
            if S[h][w] == ".":
                cnt += 1
            else:
                width[h][w - cnt : w] = [cnt] * cnt
                cnt = 0
        width[h][W - cnt : W] = [cnt] * cnt
    for w in range(W):
        cnt = 0
        for h in range(H):
            if S[h][w] == ".":
                cnt += 1
            else:
                for i in range(cnt):
                    height[h - cnt + i][w] = cnt
                cnt = 0
        for i in range(cnt):
            height[H - cnt + i][w] = cnt
    answer = 0
    for h in range(H):
        for w in range(W):
            ans = width[h][w] + height[h][w] - 1
            if ans > answer:
                answer = ans
    print(answer)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


MOD = 998244353


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    height = [[0] * W for _ in range(H)]
    width = [[0] * W for _ in range(H)]

    for h in range(H):
        cnt = 0
        for w in range(W):
            if S[h][w] == ".":
                cnt += 1
            else:
                width[h][w - cnt : w] = [cnt] * cnt
                cnt = 0
        width[h][W - cnt : W] = [cnt] * cnt
    for w in range(W):
        cnt = 0
        for h in range(H):
            if S[h][w] == ".":
                cnt += 1
            else:
                for i in range(cnt):
                    height[h - cnt + i][w] = cnt
                cnt = 0
        for i in range(cnt):
            height[H - cnt + i][w] = cnt
    answer = 0
    for h in range(H):
        for w in range(W):
            ans = width[h][w] + height[h][w] - 1
            if ans > answer:
                answer = ans
    print(answer)


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

h,w = map(int,input().split())
a = []
for i in range(h):
    a.append(list(map(int,input().split())))
chk = []
for i in range(h):
    if i % 2 == 0:
        tmp = [(i,j) for j in range(w)]
    else:
        tmp = [(i,w-j-1) for j in range(w)]
    chk += tmp
log = []
while len(chk) != 1:
    c = chk.pop(0)
    if a[c[0]][c[1]] % 2 == 1:
        a[chk[0][0]][chk[0][1]] += 1
        log.append([c[0]+1,c[1]+1,chk[0][0]+1,chk[0][1]+1])
print(len(log))
for l in log:
    print(" ".join(map(str,l)))

### FIXED CODE ###

h,w = map(int,input().split())
a = []
for i in range(h):
    a.append(list(map(int,input().split())))
chk = []
for i in range(h):
    if i % 2 == 0:
        tmp = [(i,j) for j in range(w)]
    else:
        tmp = [(i,w-j-1) for j in range(w)]
    chk += tmp
log = []
for i in range(len(chk)-1):
    c = chk[i]
    nc = chk[i+1]
    if a[c[0]][c[1]] % 2 == 1:
        a[c[0]][c[1]] -= 1
        a[nc[0]][nc[1]] += 1
        log.append(" ".join(map(str,[c[0]+1,c[1]+1,nc[0]+1,nc[1]+1])))
print(len(log))
for l in log:
    print(l)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

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

if S[0]!='B' or S[-1]!='B':
    print(0)
    exit()

mod = 10**9 + 7
cnt_l = 1
pre_s = 'B'
pre_d = 1 #1がleft
ans = 1

for i in range(1,N*2):
    s = S[i]

    if pre_s==s:
        if pre_d==1:
            d = 0
            ans *= (cnt_l*2 - i)%mod #ここまでに出てきたLeftの総数 - ここまでに出てきたrightの総数
        else:
            d = 1
            cnt_l += 1
    else:
        if pre_d==1:
            d = 1
            cnt_l += 1
        else:
            d = 0
            ans *= (cnt_l*2 - i)%mod #ここまでに出てきたLeftの総数 - ここまでに出てきたrightの総数
    pre_s = s
    pre_d = d
import math
k = math.factorial(N)
if cnt_l!=N:
    print(0)
    exit()

print(ans*k%mod)

### FIXED CODE ###

import math
n = int(input())
S = input()
 
RL = [None]*2*n
 
for i in range(2*n):
    if i % 2 == 0:
        if S[i] == 'B':
            RL[i] = 'L'
        else:
            RL[i] = 'R'
 
    else:
        if S[i] == 'B':
            RL[i] = 'R'
        else:
            RL[i] = 'L'
 
if S[0] == 'W' or S[-1] == 'W':
    print(0)
    exit()
 
left = 0
count = 1
mod = 10**9 + 7
 
for check in RL:
    if check == 'L':
        left += 1
    else:
        count = count * left % mod
        left -= 1
 
    if left < 0:
        print(0)
        exit()
 
count = count * math.factorial(n) % mod
 
if left != 0:
    print(0)
else:
    print(count)
### BUGGY CODE ###

from collections import Counter

n, q = list(map(int, input().split()))
cnt = Counter()
for _ in range(q):
    a, v = list(map(int, input().split()))
    cnt[a] += v
    mx = max(cnt.values())
    if mx == 0:
        print("1 0")
    else:
        print(str(min([key for key, value in cnt.items() if value == mx])) + ' ' + str(mx))

### FIXED CODE ###

n, q = list(map(int, input().split()))
cnt = [0 for _ in range(n + 1)]
cnt[0] = -9999999999
mx = [0, cnt[0]]


def spam():
    max_v = max(cnt)
    idx = min([i for i, value in enumerate(cnt) if value == max_v])
    return idx, max_v

for _ in range(q):
    a, v = list(map(int, input().split()))
    cnt[a] += v
    if mx[0] == a and v > 0:
        mx[1] += v

    elif mx[0] == a:
        mx[0], mx[1] = spam()

    elif mx[1] < cnt[a]:
        mx[0], mx[1] = a, cnt[a]

    elif mx[1] == cnt[a] and mx[0] > a:
        mx[0], mx[1] = a, cnt[a]

    print("%d %d" % (mx[0], mx[1]))
### BUGGY CODE ###

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

tmp_pre = 0
for i in range(1, N+1):
  tmp = (A*i)//B - A*(i//B)
  if tmp > tmp_pre:
    tmp_pre = tmp
print(int(tmp_pre))

### FIXED CODE ###

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

if B==1:
  print(0)
else:
  tb = B - 1
  tp_pre = 0
  while(True):
    tp = (A*tb)//B - A*(tb//B)
    if tp > tp_pre:
      tp_pre = tp
    tb += B
    if tb > N:
      break
  if (B > N):
    print((A*N)//B - A*(N//B))
  else:
    print(int(tp_pre))
### BUGGY CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
A=n1()

left=[]
for i in range(n-1):
    c=[0]*n
    c[i]=1
    c[i+1]=1
    left.append(c)
left.append([1]+[0]*(n-2)+[1])

from numpy.linalg import solve
 
A2=[2*i for i in A]
 
ans=solve(left, A2)
ans2=[int(i) for i in ans]
print(*ans2)

### FIXED CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
A=n1()

ans=[0]*n

ans[0]=sum([A[i]*((-1)**i) for i in range(n)])
for i in range(1,n):
    ans[i]=2*A[i-1]-ans[i-1]
print(*ans)
### BUGGY CODE ###

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

cnt = 0
for i in range(N):
    flag = False
    for j in range(0, i):
        if P[i] <= P[j]:
            #print(":", i, P[i], P[j])
            continue
        else:
            flag = True
            break
    if flag:
        continue
    else:
        #print("::", i, P[i])
        cnt += 1

print(cnt)

### FIXED CODE ###

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

cnt = 0
last = float('inf')
for i in range(N):
    if P[i] < last:
        cnt += 1
        last = P[i] 

print(cnt)
### BUGGY CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    s = [int(v) if v != "?" else -1 for v in list(str(input().rstrip('\n')))]
    dp = [[0] * 13 for _ in range(2)]
    mod = 10 ** 9 + 7

    for i in range(1):
        if s[-i-1] == -1:
            for j in range(10):
                dp[0][j % 13] += 1
        else:
            dp[0][s[-i - 1] % 13] += 1

    for i in range(1, len(s)):
        m = pow(10, i, 13)
        if s[-i-1] == -1:
            for j in range(10):
                mj = m * j
                for k in range(13):
                    dp[1][(mj + k) % 13] += dp[0][k]
        else:
            for k in range(13):
                dp[1][(m * s[-i-1] + k) % 13] += dp[0][k]
        for j in range(13):
            dp[0][j] = dp[1][j] % mod
            dp[1][j] = 0
    print(dp[0][5] % mod)


if __name__ == '__main__':
    slove()


### FIXED CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    s = [int(v) if v != "?" else -1 for v in list(str(input().rstrip('\n')))]
    dp = [[0] * 13 for _ in range(2)]
    mod = 10 ** 9 + 7

    for i in range(1):
        if s[-i-1] == -1:
            for j in range(10):
                dp[0][j % 13] += 1
        else:
            dp[0][s[-i - 1] % 13] += 1

    for i in range(1, len(s)):
        m = pow(10, i, 13)
        if s[-i-1] == -1:
            for j in range(10):
                mj = m * j
                for k in range(13):
                    dp[1][(mj + k) % 13] += dp[0][k]
        else:
            for k in range(13):
                dp[1][(m * s[-i-1] + k) % 13] += dp[0][k]
        for j in range(13):
            dp[0][j] = dp[1][j] % mod
            dp[1][j] = 0
    print(dp[0][5] % mod)


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

import heapq
class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)
 
    def pop(self):
        return heapq.heappop(self.hq) * self.sign
 
    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)
 
    def top(self):
        return self.hq[0] * self.sign

def resolve():
    n,k  = map(int,input().split())
    
    member_cost = list(map(int,input().split()))
    food_cost = list(map(int,input().split()))

    member_cost.sort()
    food_cost.sort(reverse=True)
    total_cost = []
    for i in range(len(member_cost)):
        total_cost.append(member_cost[i]*food_cost[i])

    total_cost_heap = Heapq(total_cost,True)
    if k >= sum(member_cost):
        print(0)
    else:
        while k > 0:
            k -= 1
            max_cost  = total_cost_heap.pop()
            reduce_index = total_cost.index(max_cost)
            member_cost[reduce_index] -= 1
            total_cost[reduce_index] -= food_cost[reduce_index]
            total_cost_heap.push(total_cost[reduce_index])
        print(max(total_cost))
        
            
resolve()

### FIXED CODE ###

class Contest:
    def __init__(self, member_cost,food_cost,k):
        self.member_cost = member_cost
        self.food_cost   = food_cost
        self.max_training_times = k
        
    def canAchieve(self,target):
        sum_training_times = 0
        for i in range(len(self.member_cost)):
            sum_training_times += max(0,self.member_cost[i] - target//self.food_cost[i])

        return  sum_training_times <= self.max_training_times
        


    def bisect(self,begin,end):
        if (end - begin <= 1 ):
            return end
        target = (begin + end)//2
        if self.canAchieve(target):
            return self.bisect(begin,target)

        else:
            return self.bisect(target,end)




def resolve():
    n,k  = map(int,input().split())
    
    member_cost = list(map(int,input().split()))

    food_cost = list(map(int,input().split()))
    member_cost.sort()
    food_cost.sort(reverse=True)
    total_cost = []
    for i in range(len(member_cost)):
        total_cost.append(member_cost[i]*food_cost[i])

    max_total_cost = max(total_cost)
    contest = Contest(member_cost,food_cost,k)
    print(contest.bisect(-1,max_total_cost))
    
resolve()
### BUGGY CODE ###

def main():
    import numpy as np
    import scipy.sparse.csgraph as sp
    n=int(input())
    p=np.array([np.array(list(map(int,input().split()))) for _ in [0]*n])
    abc=[]
    ans=0
    for i in range(n):
        for j in range(i+1,n):
            b=p[i][j]
            for k in range(n):
                if i==k or j==k:
                    continue
                if b==p[i][k]+p[k][j]:
                    break
            else:
                abc.append([i,j,b])
                abc.append([j,i,b])
                ans+=b
    inf=float('inf')
    d=np.full((n,n),inf)
    for i in range(n):d[i][i]=0
    for a,b,c in abc:
        d[a][b]=c
        d[b][a]=c
    s=sp.shortest_path(d)
    if (s==p).all():
        print(ans)
    else:
        print(-1)
main()

### FIXED CODE ###

def main():
    n=int(input())
    if n==1:
        print(0)
        return 0
    import numpy as np
    p=np.array([np.array(list(map(int,input().split()))) for _ in [0]*n])
    if n==2:
        print(p[0][1])
        return 0
    import scipy.sparse.csgraph as sp
    ans=0
    d=np.full((n,n),0)
    for i in range(n):
        for j in range(i+1,n):
            b=p[i][j]
            if b!=np.sort(p[i]+p[j])[2]:
                d[i][j],d[j][i]=b,b
                ans+=b
    s=sp.shortest_path(d)
    if (s==p).all():
        print(ans)
    else:
        print(-1)
main()
### BUGGY CODE ###

from math import factorial
S = input()
cum = []
for i in range(len(S)-1, -1, -1):
    n = int(S)
    n = n % 10**(i+1)
    cum.append(n % 2019)
cum = sorted(cum)

prev = cum[0]
ans = 0
cnt = 0
for c in cum:
    if c != prev:
        if prev == 0:
            ans += cnt
        ans += cnt * (cnt-1) // 2
        cnt = 1
    else:
        cnt += 1
    prev = c

if cnt > 1:
    if prev == 0:
        ans += cnt
    ans += cnt * (cnt-1) // 2
    cnt = 1

print(ans)

### FIXED CODE ###

import sys
import math
from collections import deque
from collections import Counter

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    S = SI()
    l = len(S)
    T = [0] * (l+1)
    inv_S = S[::-1]
    for i, s in enumerate(inv_S):
        s = int(s)
        T[i+1] = (T[i] + s * pow(10, i, 2019)) % 2019
    C = Counter(Counter(T).values())
    ans = 0
    for n, x in C.items():
        if n == 1: continue
        ans += cmb(n, 2) * x
    print(ans)


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

N, X, Y = map(int, input().split())


count = [0] * (N-1)
for i in range(1, N+1):
    for j in range(i+1, N+1):
        routeA = abs(j-i)
        routeB = abs(X-i) + abs(Y-j) + 1
        routeC = abs(Y-i) + abs(X-j) + 1
        min_route = min(routeA, routeB, routeC)
        count[min_route - 1] += 1

print('\n'.join(map(str, count)))

### FIXED CODE ###

N, X, Y = map(int, input().split())


count = [0] * (N-1)
for i in range(1, N+1):
    for j in range(i+1, N+1):
        routeA = abs(j-i)
        routeB = abs(X-i) + abs(Y-j) + 1
        min_route = min(routeA, routeB)
        count[min_route - 1] += 1

print('\n'.join(map(str, count)))
### BUGGY CODE ###

import numpy as np

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7

ans = 0

for i in range(60):
    cnt = 0
    for a in A:
        cnt += a>>i&1
    ans += cnt*(N-cnt)*2**i
    ans %= mod
    # print(ans)
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7

ans = 0

for i in range(60):
    cnt = 0
    for a in A:
        cnt += a>>i&1
    ans += cnt*(N-cnt)*2**i
    ans %= mod
    # print(ans)
print(ans)
### BUGGY CODE ###

import heapq
N, M = map(int, input().split())
*A, = map(int, input().split())
BC = [list(map(int, input().split())) for _ in range(M)]
hq = []
for i in range(N):
    heapq.heappush(hq, A[i])

for bc in BC:
    for i in range(bc[0]):
        tmp = heapq.heappop(hq)
        if tmp < bc[1]:
            heapq.heappush(hq, bc[1])
        else:
            heapq.heappush(hq, tmp)

print(sum(hq))

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
*A, = map(int, input().split())
BC = [list(map(int, input().split())) for _ in range(M)]
BC = list(reversed(sorted(BC, key=lambda x:x[1])))
#print(BC)
hq = []
for i in range(N):
    heapq.heappush(hq, A[i])

flag = False
for bc in BC:
    for i in range(bc[0]):
        tmp = heapq.heappop(hq)
        if tmp < bc[1]:
            heapq.heappush(hq, bc[1])
        else:
            heapq.heappush(hq, tmp)
            flag = True
            break
    if flag:
        break

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

n = int(input())
ans = 0
for i in range(1,n):
    ans += i
print(ans)

### FIXED CODE ###

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

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

mod = 10 ** 9 + 7

N = int(input())
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  A, B = 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)

### FIXED CODE ###

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

mod = 10 ** 9 + 7

N = int(input())
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  A, B = 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)