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

N, K = map(int, raw_input().split())
ps = []
for i in xrange(N):
  ps.append(map(int, raw_input().split()))

xsorted = sorted(ps, key=lambda p: p[0])
ysorted = sorted(ps, key=lambda p: p[1])

ans = float('inf')
for i in xrange(N):
  bottom = ysorted[i][1]
  for j in xrange(i+K-1, N):
    top = ysorted[j][1]
    for k in xrange(N):
      right = xsorted[k][0]
      for l in xrange(k+K-1, N):
        left = xsorted[l][0]
        c = 0
        for a in xrange(N):
          if right <= ps[a][0] <= left and bottom <= ps[a][1] <= top:
            c += 1
            if c >= K: break
        else:
          continue
        area = (left - right) * (top - bottom)
        if area < ans:
          ans = area

print ans

### FIXED CODE ###

N, K = map(int, raw_input().split())
ps = []
for i in xrange(N):
  ps.append(map(int, raw_input().split()))

xsorted = zip(*sorted(ps, key=lambda p: p[0]))[0]
ysorted = zip(*sorted(ps, key=lambda p: p[1]))[1]

ans = float('inf')
for i in xrange(N):
  bottom = ysorted[i]
  for j in xrange(i+K-1, N):
    top = ysorted[j]
    for k in xrange(N):
      if k+K-1 >= N:
        break
      right = xsorted[k]
      # 2 bun tansaku
      f, t = k+K-1, N
      sol = None
      while True:
        mid = (f+t)//2
        left = xsorted[mid]
        c = 0
        for p in ps:
          if right <= p[0] <= left and bottom <= p[1] <= top:
            c += 1
            if c >= K: break
        else:
          if f+1 >= t:
            break
          f = mid
          continue
        sol = mid
        if f+1 >= t:
          break
        t = mid
      if sol:
        area = (xsorted[sol] - right) * (top - bottom)
        if area < ans:
          ans = area

print ans
### BUGGY CODE ###

import sys
input = sys.stdin.readline
S = input().strip()
mod = 10**9+7
a = 0
ab = 0
ans = 0
q = 1
for c in S:
    if c == 'A':
        a += q
    elif c == 'B':
        ab += a
    elif c == 'C':
        ans += ab
    elif c == '?':
        a, ab, ans, q = a*3+q, ab*3+a, ans*3+ab, q*3
print(ans % mod)


### FIXED CODE ###

import sys
input = sys.stdin.readline
S = input().strip()
mod = 10**9+7
a = 0
ab = 0
ans = 0
q = 1
for c in S:
    if c == 'A':
        a += q
    elif c == 'B':
        ab += a
    elif c == 'C':
        ans += ab
    elif c == '?':
        a, ab, ans, q = a*3+q, ab*3+a, ans*3+ab, q*3
    a %= mod
    ab %= mod
    ans %= mod
    q %= mod
print(ans % mod)
### BUGGY CODE ###

import sys
def prime(n):
  i = 2
  if n == 1:
    l = []
  else:
    l = [2]
  while i < n:
    i += 1
    for j in l:
      if i % j == 0:
        break
    else:
      l.append(i)
  return len(l)
for line in sys.stdin.readlines():
  n = int(line)
  print(prime(n))

### FIXED CODE ###

lst = [1 for i in range(10 ** 6 + 1)]
lst[0] = lst[1] = 0
for i in range(10 ** 6 + 1):
  if lst[i] == 1:
    for j in range(i * 2, 10 ** 6 + 1, i):
      lst[j] = 0
while 0 == 0:
  try:
    n = int(input())
    c = 0
    for i in range(n + 1):
      c += lst[i]
    print(c)
  except EOFError:
    break
### BUGGY CODE ###

h, w, k = map(int, input().split())
s = [input() for _ in range(h)]

minimum = (h - 1) * (w - 1)
for div_h in range(1 << (h - 1)):
  h_index = [0] * h
  cur_index = 0
  bin_h = format(div_h, '0{}b'.format(h-1))
  for i in range(1, h):
    if bin_h[-i] == '1':
      cur_index += 1
    h_index[i] = cur_index
  white_choco = [0] * (cur_index + 1)
  divide = 0
  j = 0
  while j < w:
    for i in range(h):
      if s[i][j] == '1':
        h_i = h_index[i]
        if white_choco[h_i] < k:
          white_choco[h_i] += 1
        else:
          break
    else:
      j += 1
      continue
    white_choco = [0] * (cur_index + 1)
    divide += 1
  minimum = min(minimum, divide + cur_index)
print(minimum)

### FIXED CODE ###

h, w, k = map(int, input().split())
s = [[int(s_ij) for s_ij in input()] for _ in range(h)]

minimum = (h - 1) * (w - 1)
for div_h in range(1 << (h - 1)):
  h_index = [0] * h
  cur_index = 0
  mask = 1 << (h - 2)
  for i in range(1, h):
    if div_h & mask:
      cur_index += 1
    h_index[i] = cur_index
    mask >>= 1
  white_choco = [0] * (cur_index + 1)
  divide = 0
  j = 0
  flag = False
  while j < w:
    for i in range(h):
      white_choco[h_index[i]] += s[i][j]
    if max(white_choco) > k:
      if flag:
        break
      flag = True
      white_choco = [0] * (cur_index + 1)
      divide += 1
    else:
      j += 1
      flag = False
  else:
    minimum = min(minimum, divide + cur_index)
print(minimum)
### BUGGY CODE ###

import sys
import bisect
readline = sys.stdin.readline

def main():
	a = [1,2,3,4,5]
	n = int(input())
	s = tuple(input())

	ans = 0
	r = []
	g = []
	b = []
	for i in range(3):
		if s[i] == 'R':
			r.append(i)
		elif s[i] == 'G':
			g.append(i)
		else:
			b.append(i)

	for i in range(3,n):
		if s[i] == 'R':
			r.append(i)
		elif s[i] == 'G':
			g.append(i)
		else:
			b.append(i)

		for j in range(i-2):
			if s[i] == s[j]:
				continue
			elif 'R' not in [s[i],s[j]]:
				ans += bisect.bisect_left(r,i) - bisect.bisect_left(r,j)
				index = bisect.bisect_left(r,j + (i-j)//2 )
				if index < len(r):
					if (i-j) % 2 == 0 and r[index] == j + (i-j)//2:
						ans -= 1
			elif 'G' not in [s[i],s[j]]:
				ans += bisect.bisect_left(g,i) - bisect.bisect_left(g,j)
				index = bisect.bisect_left(g,j + (i-j)//2 )
				if index < len(g):
					if (i-j) % 2 == 0 and g[index] == j + (i-j)//2:
						ans -= 1
			elif 'B' not in [s[i],s[j]]:
				ans += bisect.bisect_left(b,i) - bisect.bisect_left(b,j)
				index = bisect.bisect_left(b,j + (i-j)//2 )
				if index < len(b):
					if (i-j) % 2 == 0 and b[index] == j + (i-j)//2:
						ans -= 1

	print(ans)

if __name__ == '__main__':
	main()


### FIXED CODE ###

import sys
import bisect
readline = sys.stdin.readline

def main():
	n = int(input())
	s = tuple(input())

	ans = 0
	r = []
	g = []
	b = []
	for i in range(3):
		if s[i] == 'R':
			r.append(i)
		elif s[i] == 'G':
			g.append(i)
		else:
			b.append(i)

	for i in range(3,n):
		if s[i] == 'R':
			r.append(i)
		elif s[i] == 'G':
			g.append(i)
		else:
			b.append(i)

		for j in range(i-2):
			if (j-i) % 2 == 0:
				if s[i] == s[j]:
					continue
				elif 'R' not in [s[i],s[j]]:
					ans += bisect.bisect_left(r,i) - bisect.bisect_left(r,j)
					index = bisect.bisect_left(r,j + (i-j)//2 )
					if index < len(r):
						if r[index] == j + (i-j)//2:
							ans -= 1
				elif 'G' not in [s[i],s[j]]:
					ans += bisect.bisect_left(g,i) - bisect.bisect_left(g,j)
					index = bisect.bisect_left(g,j + (i-j)//2 )
					if index < len(g):
						if g[index] == j + (i-j)//2:
							ans -= 1
				elif 'B' not in [s[i],s[j]]:
					ans += bisect.bisect_left(b,i) - bisect.bisect_left(b,j)
					index = bisect.bisect_left(b,j + (i-j)//2 )
					if index < len(b):
						if b[index] == j + (i-j)//2:
							ans -= 1
			else:
				if s[i] == s[j]:
					continue
				elif 'R' not in [s[i],s[j]]:
					ans += bisect.bisect_left(r,i) - bisect.bisect_left(r,j)

				elif 'G' not in [s[i],s[j]]:
					ans += bisect.bisect_left(g,i) - bisect.bisect_left(g,j)

				elif 'B' not in [s[i],s[j]]:
					ans += bisect.bisect_left(b,i) - bisect.bisect_left(b,j)


	print(ans)

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

Num , Sum =  map(int,input().split())
count = 0
check = 0

for x in range(Num+1):
    for y in range ( Num+1 ):

        if (Sum - x)  >  Num * 2:
            break
        elif 0 <= (Sum - x ) - y <= Num :
            count += 1

print(count)

### FIXED CODE ###

Num , Sum =  map(int,input().split())
count = 0
check = 0

for x in range(Num+1):
    for y in range ( Num+1 ):

        if 0 <= (Sum - x ) - y <= Num :
            count += 1

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

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

answer = n

for i in range(n + 1):
    answer = min(answer, s[:i].count("#") + s[i:].count("."))

print(answer)



### FIXED CODE ###

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


left_black = 0
right_white = s.count(".")
answer = left_black + right_white

for w in s:
    if w == "#":
        left_black += 1
    else:
        right_white -= 1
    answer = min(answer, left_black + right_white)

print(answer)
### BUGGY CODE ###

from collections import deque
#import time
#start = time.time()#計測始

s = str(input())
n=len(s)
span :int=1
mlist=deque("0")
slist :str=""

while span<int(n)+1:
  slist = str(s[n-span]) + slist
  #print(str(slist))
  m = int(slist)%2019
  mlist.append(str(m))
  span+=1

ll=len(mlist)
l=len(set(mlist))
print(ll-l)
#end = time.time()#計測終
#print(f"{end-start}sec.")#計測出力

### FIXED CODE ###

import time

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

#start = time.time()#計測始
ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
#end = time.time()#計測終
#print(f"{end-start}sec.")#計測出力
### BUGGY CODE ###

import heapq
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, M, S = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    edge[u].append((v, a, b))
    edge[v].append((u, a, b))
CD = tuple(tuple(map(int, input().split())) for _ in range(N))

inf = 10**18
U = N*50
S = min(S, U)
dist = [[inf] * (U + 1) for _ in range(N)]
dist[0][S] = 0

que = [(0, 0, S)]  # 時間、現在地、銀貨の数
while que:
    time, now, silver = heapq.heappop(que)
    if dist[now][silver] < time:
        continue
    # 両替する
    c, d = CD[now]
    for i in range(1, U + 1):
        if silver + i > U:
            break
        t = (i + c - 1) // c * d
        if dist[now][silver + i] > time + t:
            dist[now][silver + i] = time + t
            heapq.heappush(que, (time + t, now, silver + i))

    # 移動する
    for nxt, s, t in edge[now]:
        if silver < s:
            continue
        if dist[nxt][silver - s] > time + t:
            dist[nxt][silver - s] = time + t
            heapq.heappush(que, (time + t, nxt, silver - s))

for i in range(1, N):
    print(min(dist[i]))

### FIXED CODE ###

import heapq
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, M, S = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    edge[u].append((v, a, b))
    edge[v].append((u, a, b))
CD = tuple(tuple(map(int, input().split())) for _ in range(N))

inf = 10**18
U = N*50
S = min(S, U)
dist = [[inf] * (U + 1) for _ in range(N)]
dist[0][S] = 0

que = [(0, -S, 0)]  # 時間、現在地、銀貨の数
while que:
    time, silver, now = heapq.heappop(que)
    silver = -silver
    if dist[now][silver] < time:
        continue
    # 両替する
    c, d = CD[now]
    n = 1
    while silver + c * n <= U:
        if dist[now][silver + c * n] > time + n * d:
            dist[now][silver + c * n] = time + n * d
            heapq.heappush(que, (time + n * d, -(silver + c * n), now))
            n += 1
        else:
            break
    # 移動する
    for nxt, s, t in edge[now]:
        if silver < s:
            continue
        if dist[nxt][silver - s] > time + t:
            dist[nxt][silver - s] = time + t
            heapq.heappush(que, (time + t, -(silver - s), nxt))

for i in range(1, N):
    print(min(dist[i]))
### BUGGY CODE ###

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

MOD = 10**9 + 7

dig = 60
Abn = [[0]*dig for _ in range(n)]

for i in range(n):
  for j in range(dig):
    if A[i]>>j&1:
      Abn[i][j] = 1
      

Cbn0 = [[0]*dig for i in range(n)]
Cbn1 = [[0]*dig for i in range(n)]

for j in range(dig):
  if Abn[n-1][j]==1:
    Cbn1[n-1][j] = 1
  else:
    Cbn0[n-1][j] = 1
    
for i in range(n-2, 0, -1):
  for j in range(dig):
    if Abn[i][j]==1:
      Cbn0[i][j] = Cbn0[i+1][j]
      Cbn1[i][j] = Cbn1[i+1][j] + 1
    else:
      Cbn0[i][j] = Cbn0[i+1][j] + 1
      Cbn1[i][j] = Cbn1[i+1][j]

ans = 0
two = [pow(2, i, MOD) for i in range(dig)]

for i in range(n-1):
  for j in range(dig):
    if Abn[i][j] == 1:
      ans += Cbn0[i+1][j] * two[j] % MOD
    else:
      ans += Cbn1[i+1][j] * two[j] % MOD
    ans %= MOD
    
print(ans)


### FIXED CODE ###

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

MOD = 10**9 + 7

dig = 60
Abn = [[0]*dig for _ in range(n)]

b0 = [0]*dig
b1 = [0]*dig
for i in range(n):
  for j in range(dig):
    if A[i]>>j&1:
      b1[j] += 1
    else:
      b0[j] += 1
      
pow2 = [pow(2, i, MOD) for i in range(dig)]

ans = 0
for i in range(dig):
  ans += b1[i]*b0[i]*pow2[i]%MOD
  
print(ans%MOD)
### BUGGY CODE ###

import math

input1 = input()
kbai= int(input1)
 
input2=input().split(" ")
mins= int(input2[0])
maxs= int(input2[1])
flg=0
ans=0
tmp=0

tmp=math.floor(mins/kbai)
ans=tmp*kbai
#print(tmp)

while flg == 0:
  ans=ans+kbai
  if ans > mins and ans <= maxs:
    flg=1

if flg ==1:
  print("OK")
  #print(ans,maxs,mins,flg)
else:
  print("NG")
  #print(ans,maxs,mins,flg)


### FIXED CODE ###

#
#at coder beginner contest165 a we love golf
#
import math

input1 = input()
kbai= int(input1)
 
input2=input().split(" ")
mins= int(input2[0])
maxs= int(input2[1])
flg=0
ans=0
tmp=0

tmp=math.floor(mins/kbai)
ans=tmp*kbai
#print(tmp)

while ans <= maxs:
  if ans >= mins and ans <= maxs:
    flg=1
  ans=ans+kbai

if flg ==1:
  print("OK")
  #print(ans,maxs,mins,flg)
else:
  print("NG")
  #print(ans,maxs,mins,flg)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H,W = map(int,input().split())
Gd = [list(input()) for _ in range(H)]
L = [[0]*W for _ in range(H)]
R = [[0]*W for _ in range(H)]
U = [[0]*W for _ in range(H)]
D = [[0]*W for _ in range(H)]
for h in range(H):
  for w in range(W):
    if Gd[h][w]=='#':
      R[h][w]=0
    else:
      if w==0:
        R[h][w]=1
      else:
        R[h][w]=R[h][w-1]+1
    wr=W-w-1
    if Gd[h][wr]=='#':
      L[h][wr]=0
    else:
      if w==0:
        L[h][wr]=1
      else:
        L[h][wr]=L[h][wr+1]+1

for w in range(W):
  for h in range(H):
    if Gd[h][w]=='#':
      D[h][w]=0
    else:
      if h==0:
        D[h][w]=1
      else:
        D[h][w]=D[h-1][w]+1
    hr=H-h-1
    if Gd[hr][w]=='#':
      U[hr][w]=0
    else:
      if h==0:
        U[hr][w]=1
      else:
        U[hr][w]=U[hr+1][w]+1
ret = 0
for w in range(W):
  for h in range(H):
    ret = max(ret, D[h][w]+U[h][w]+R[h][w]+L[h][w]-3)
print(ret)

### FIXED CODE ###

import numpy as np
H,W = map(int,input().split())
HL=list(range(H))
WL=list(range(W))
Gd = np.array([list(input()) for _ in HL])
Gd = np.where(Gd=='.', 1, 0)
L=np.zeros((H,W),dtype=np.int64)
R=np.zeros((H,W),dtype=np.int64)
U=np.zeros((H,W),dtype=np.int64)
D=np.zeros((H,W),dtype=np.int64)

for w in WL:
  R[:,w]=(R[:,w-1]+1)*Gd[:,w]
  L[:,-w-1]=(L[:,-w]+1)*Gd[:,-w-1]
for h in HL:
  D[h,:]=(D[h-1,:]+1)*Gd[h,:]
  U[-h-1,:]=(U[-h,:]+1)*Gd[-h-1,:]
print(np.max(D+U+L+R-3))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

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

mem = {}
def rec(arr):
    if len(arr)==1:
        if arr[0] == 1:
            return [1]
        else:
            return False
    h = hash(tuple(arr))
    if h in mem:
        return mem[h]
    for i,a in enumerate(arr):
        if i+1 == a:
            _arr = arr[:]
            del _arr[i]
            res = rec(_arr)
            if res:
                res.append(i+1)
                mem[h] = res
                break
    else:
        mem[h] = False
    return mem[h]

ans = rec(B)
if ans:
    print(*ans,sep='\n')
else:
    print(-1)

### FIXED CODE ###

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

ans = []
while B:
    for i,a in reversed(list(enumerate(B))):
        if i+1 == a:
            ans.append(a)
            del B[i]
            break
    else:
        print(-1)
        exit()
print(*ans[::-1], sep='\n')
### BUGGY CODE ###

H, W = map(int, input().split())

S = []
for i in range(H):
    S.append(input())

U = [[0] * W for h in range(H)]
D = [[0] * W for h in range(H)]
L = [[0] * W for h in range(H)]
R = [[0] * W for h in range(H)]

for h in range(H):
    for w in range(W):
        if S[h][w] == 1:
            continue
        # up
        if h-1 < 0 or S[h-1][w] == '#':
            U[h][w] = 0
        else:
            U[h][w] = U[h-1][w] + 1
        # left
        if w-1 < 0 or S[h][w-1] == '#':
            L[h][w] = 0
        else:
            L[h][w] = L[h][w-1] + 1

for h in range(H-1, -1, -1):
    for w in range(W-1, -1, -1):
        if S[h][w] == 1:
            continue
        # down
        if h+1 >= H or S[h+1][w] == '#':
            D[h][w] = 0
        else:
            D[h][w] = D[h+1][w] + 1
        # right
        if w+1 >= W or S[h][w+1] == '#':
            R[h][w] = 0
        else:
            R[h][w] = R[h][w+1] + 1

ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            continue
        cnt = U[h][w] + L[h][w] + D[h][w] + R[h][w] + 1
        if cnt > ans:
            ans = cnt

print(ans)


### FIXED CODE ###

H, W = map(int, input().split())

S = []
for i in range(H):
    S.append(input())

U = [[0] * W for h in range(H)]
D = [[0] * W for h in range(H)]
L = [[0] * W for h in range(H)]
R = [[0] * W for h in range(H)]

for h in range(H):
    for w in range(W):
        if S[h][w] == 1:
            continue
        # up
        if h-1 < 0 or S[h-1][w] == '#':
            U[h][w] = 0
        else:
            U[h][w] = U[h-1][w] + 1
        # left
        if w-1 < 0 or S[h][w-1] == '#':
            L[h][w] = 0
        else:
            L[h][w] = L[h][w-1] + 1

for h in range(H-1, -1, -1):
    for w in range(W-1, -1, -1):
        if S[h][w] == 1:
            continue
        # down
        if h+1 >= H or S[h+1][w] == '#':
            D[h][w] = 0
        else:
            D[h][w] = D[h+1][w] + 1
        # right
        if w+1 >= W or S[h][w+1] == '#':
            R[h][w] = 0
        else:
            R[h][w] = R[h][w+1] + 1

ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            continue
        cnt = U[h][w] + L[h][w] + D[h][w] + R[h][w] + 1
        if cnt > ans:
            ans = cnt

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

n = int(input())
a = list(map(int, input().split()))
from fractions import gcd
from functools import reduce
import numpy as np
def lcm(x,y):
  return (x*y)//gcd(x,y)
l = reduce(lcm, a)
mod = 10**9+7
print(sum(l//(np.array(a)))%mod)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
from fractions import gcd
from functools import reduce
def lcm(x,y):
  return (x*y)//gcd(x,y)
mod = 10**9+7
l = reduce(lcm, a) % mod
ans = 0
for i in range(n):
  ans += l * pow(a[i], mod - 2, mod)
  ans %= mod
print(ans)
### BUGGY CODE ###

from collections import Counter
S = input()
mod = 2019
p = [0] * len(S)
r = 0
for i,s in enumerate(S[::-1]):
  r += (int(s) * (10**i))%mod
  p[i] = r%mod

p.append(0)
ans = 0
c = Counter(p)
for k,n in c.most_common():
  if n > 1:
    ans += 1
  else:break
  
print(ans)

### FIXED CODE ###

S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in reversed(S):
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10%mod
  p[r] += 1

print(sum([i*(i-1)//2 for i in p]))
### BUGGY CODE ###

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


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

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

#

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


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

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

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

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

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



















if __name__ == "__main__":
	main()

### FIXED CODE ###

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


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

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

#

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


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

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

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

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

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



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

n=int(input())
s=['']*n
for i in range(n):
  s[i]=sorted(list(input()))
ans=0
for i in range(n):
  for j in range(i,n):
    if s[i]==s[j] and not i==j:
      ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
dict={}
ans=0
for i in range(n):
  s=''.join(sorted(input()))
  dict[s]=dict.get(s,-1)+1
  ans+=dict[s]
print(ans)
### BUGGY CODE ###

A, B = map(int, input().split())
while B != 0:
  A, B = B, A % B
i, j = 2, 1
g = A
while i <= g and A != 1:
  if A % i == 0:
    j += 1
    while A % i == 0:
      A //= i
  i += 1
print(j)

### FIXED CODE ###

A, B = map(int, input().split())
a, b = A, B
while b != 0:
  a, b = b, a % b
prod = 1
s = 1
p = 2
g = a
while a != 1:
  i = 0
  while a % p == 0:
    i += 1
    a //= p
    prod *= p
  if i != 0:
    s += 1
  p += 1
  if p > int(g**(1/2)) and prod != g:
    s += 1
    break
print(s)
### BUGGY CODE ###

import math
N = int(input())
for n in range(1, N+1):
    nn = int(n**0.5+1)
    ans = 0
    for x in range(1, nn):
        for y in range(1, nn):
            d = n-x*x-y*y-x*y
            if d < 0:
                break
            for z in range(1, nn):
                zz = z*z+z*(x+y)
                if d == zz:
                    ans += 1
                elif zz > d:
                    break
    print(ans)


### FIXED CODE ###

import math
N = int(input())
for n in range(1, N+1):
    nn = int(n**0.5+1)
    ans = 0
    for x in range(1, nn):
        for y in range(1, nn):
            d = n-x*x-y*y-x*y
            if d < 0:
                break
            l, r = 0, nn
            while (r-l) > 1:
                m = (r+l)//2
                z = m*m+m*(x+y)
                if z == d:
                    ans += 1
                    break
                elif z < d:
                    l = m
                else:
                    r = m
    print(ans)
### BUGGY CODE ###

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

n,k = map(int,readline().split())
h = list(map(int,readline().split()))

dp = [float('inf')]*n
dp[0] = 0

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

print(dp[n-1])

### FIXED CODE ###

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

n,k = map(int,readline().split())
h = list(map(int,readline().split()))

dp = [float('inf')]*n
dp[0] = 0

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

print(dp[n-1])