Harryxun/stf_run huggingface dataset:
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10**9 + 7
A.sort()

keisuu = [1]
for i in range(N-K):
	tmp = keisuu[-1] * (k-1-i) // (i+1)
	tmp %= mod
	keisuu.append(tmp)

tot = keisuu

tmp = 0
keisuu_sumup = []
for i in range(len(keisuu)):
	tmp += keisuu[i]
	tmp %= 0
	kesuu_sumup.append(tmp)

ans = 0
for i in range(N):
	ans -= tot * A[i]
	ans += keisuu_sumup[i] * A[K-1+i]
	ans %= mod

print(ans)

### FIXED CODE ###

import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
mod = 10**9+7
A.sort()

fact = np.zeros(N+1, np.int64)
inv = np.zeros(N+1, np.int64)

fact[0], fact[1] = 1, 1
inv[0], inv[1] = 1, 1

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

ans = 0
lim = N - K + 1
for ind, a in enumerate(A,1):
	if ind < K:
		tmp_max = 0
	else:
		r_cnt = ind - 1
		r_comb = fact[r_cnt]
		r_comb *= inv[K - 1]
		r_comb %= mod
		r_comb *= inv[r_cnt - K + 1]
		r_comb %= mod

		tmp_max= r_comb * a % mod

	if ind > lim:
		tmp_min = 0
	else:
		l_cnt = N - ind
		l_comb = fact[l_cnt]
		l_comb *= inv[K - 1]
		l_comb %= mod
		l_comb *= inv[l_cnt - K + 1]
		l_comb %= mod

		tmp_min = l_comb * a % mod

	ans += (tmp_max - tmp_min) % mod
	ans %= mod

ans %= mod
print(ans)
N = int(input())
arr = [int(x) for x in input().split()]
found = false
for x in arr:
  if x == 0:
    found = True
if found:
  print(0)
  exit(0)
res = 1
MAX = 10 ** 18
for x in arr:
  res *= x
  if res > MAX:
    print(-1)
    exit(0)
print(res)

### FIXED CODE ###

N = int(input())
arr = [int(x) for x in input().split()]
found = False
for x in arr:
  if x == 0:
    found = True
if found:
  print(0)
  exit(0)
res = 1
MAX = 10 ** 18
for x in arr:
  res *= x
  if res > MAX:
    print(-1)
    exit(0)
print(res)
N = int(input())
S = input()

ans=''
for x in S:
    nc=ord(N[x])+N
    if nc>90:
        nc-=26
    ans+=chr(nc)
print(ans)

### FIXED CODE ###

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

ans=""
for x in S:
    nc=ord(x)
    nc+=N
    if nc>90:
        nc-=26
    ans+=chr(nc)
print(ans)
s = [ord(i) - 97 for i in input()]
k = int(input())

for i in range(len(s)):
    if 26 - s[i] <= k:
        k -= 26 - s[i]
        s[i] = 0

s[-1] += k

ans = "".join(chr(i+97) for i in s)
print(ans)


### FIXED CODE ###

s = [ord(i) - 97 for i in input()]
k = int(input())

for i in range(len(s)):
    diff = 26 - s[i]
    if (s[i] != 0) and (diff <= k):
        k -= diff
        s[i] = 0

s[-1] = (s[-1] + k) % 26

ans = "".join(chr(i+97) for i in s)
print(ans)
a,b=map(int,input().split())
print((3a+b)//2)


### FIXED CODE ###

a,b=map(int,input().split())
print((3*a+b)//2)
N = int(input())
A = list(map(int, input().split()))

ans = 1
res = 0

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

for i in range(N):
    ans *= A[i]
    ans %= 10 ** 9 + 7

for i in range(N):
    res += ans * modinv(A[i], 10 ** 9 + 7)
    res %= 10 ** 9 + 7

print(res)

### FIXED CODE ###

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

mod = 10 ** 9 + 7
ans = 0

A_sum = [A[0] for i in range(N)]
for i in range(1, N):
    A_sum[i] = A_sum[i-1] + A[i]

for i in range(1, N):
    ans += A[i] * A_sum[i-1]
    ans %= mod

print(ans)
import sys
import math
input = sys.stdin.readline

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

for i in range(len(l)):
    l[i] = i - l[i] + 1

l.sort()
t = l[math.ceil(len(l) / 2)]

for i in range(len(l)):
    l[i] = abs(l[i] - t)
    
print(sum(l))

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

for i in range(len(l)):
    l[i] = i - l[i] + 1

l.sort()
t = l[int(len(l) / 2)]

for i in range(len(l)):
    l[i] = abs(l[i] - t)
    
print(sum(l))
H, N = map(int, input().split())
a = list(map(int, input8).split())
sum = sum(a)
if sum >= H:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

H, N = map(int, input().split())
a = list(map(int, input().split()))
sum = sum(a)
if sum >= H:
  print("Yes")
else:
  print("No")
(r, c) = [int(i) for i in input().split()]
last_row = [0 for _ in range(c+1)]

for _ in range(r):
    row = [int(i) for i in input().split()]
    for cc in range(c):
        last_row[cc] += int(row[cc])
        print(row[cc], end=' ')

    print(sum(row))

last_row[-1] = sum(last_row)
print(' '.join([str(a) for a in last_row])

### FIXED CODE ###

(r, c) = [int(i) for i in input().split()]
last_row = [0 for _ in range(c+1)]
 
for _ in range(r):
    row = [int(i) for i in input().split()]
    for cc in range(c):
        last_row[cc] += int(row[cc])
        print(row[cc], end=' ')
 
    print(sum(row))
 
last_row[-1] = sum(last_row)
print(' '.join([str(a) for a in last_row]))
N, K = [int(x) for x in input().split(' ')]
m = 10**9 + 7
import math
def combination(n, r):
  return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
  
for k in range(1, n+1):
  print(combination(N-K+1, k) % m * combination(K-1, k-1) % m)


### FIXED CODE ###

N, K = [int(x) for x in input().split(' ')]
m = 10**9 + 7
fact = [1] * (N+1)
for i in range(1, N+1):
  fact[i] = fact[i-1] * i
  
def combination(n, r):
  return fact[n] // fact[r] // fact[n-r]
  
for k in range(1, K+1):
  print(combination(N-K+1, k) % m * combination(K-1, k-1) % m)
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
import random
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

# popcount table
popcount = {}
popcount[0] = 0
def gpc(n):
    if n not in popcount:
        popcount[n] = bin(n).count("1")
    return popcount[n]

# mem rec
solutions = {}
def sol(Xk):
    # pc = popcount[Xk]
    pc = gpc(Xk)
    # print("Call {}, {}".format(Xk, pc))
    if Xk == 0:
        solutions[(Xk, 0)] = 0
        return 0
    elif (Xk, pc) in solutions:
        return solutions[Xk, pc]
    else:
        count = 1 + sol(Xk % pc)
        solutions[Xk, pc] = count
        return count

def main():
    from builtins import int, map
    N = int(input())
    X = input()
    
    # 余りが0からN - 1
    Xpc = X.count("1")
    iX = int(X, 2)
    rem_groups = [0] * N
    for k in range(1, N):
        # print(k, gpc(k), k % gpc(k))
        rem_groups[k] = k % gpc(k)

    # ans = [-1] * (N + 1)
    for k in range(N - 1, -1, -1):
        # f(k)を計算
        Xk = iX ^ (1 << k)
        Xkpc = Xpc
        if (iX & (1 << k)) >> k:
            Xkpc -= 1
        else:
            Xkpc += 1
        ans = rem_groups[Xk % Xkpc] + 1 + (0 if Xk % Xkpc == 0 else 1)
        # ans_sol = sol(Xk)
        # print(k, Xk, Xkpc, ans, ans_sol)
        print(ans)



if __name__ == '__main__':
    main()

### FIXED CODE ###

N = int(input())
B = input()

B_1 = B.count("1") # pc
mod_p1 = int(B, 2) % (B_1 + 1) # pc + 1
if B_1 != 1:
    mod_m1 = int(B, 2) % (B_1 - 1) # pc - 1

# 小さい数字は直接計算しても一瞬
def calc_small(n, count):
    count += 1
    mod = n % bin(n).count("1")
    if mod == 0:
        return count
    else:
        return calc_small(mod, count)

for i in range(N):
    if B_1 == 1 and int(B[i]) == 1:
        print(0)
        continue

    # はBiが1か0かで，元のmodから差分計算できる
    if B[i] == '1':
        # 反転して-する場合 (mod PC - 1)
        mod = (mod_m1 - pow(2, N - i - 1, B_1 - 1)) % (B_1 - 1)
    else:
        # 反転して+する場合 (mod PC + 1)
        mod = (mod_p1 + pow(2, N - i - 1, B_1 + 1)) % (B_1 + 1)
    count = 1
    if mod == 0:
        print(count)
    else:
        print(calc_small(mod, count))
import sys

S = input()
K = int(input())

if len(S) == 1:
    print(K//2)
    sys.exit()
if len(S) == 2:
    if S[0] == S[1]:
        print(K)
    else:
        print('0')
    sys.exit()

olds = S[0]
l = 1
c = 0
first = 1
for i in range(1,len(S)):

    if olds == S[i]:
        l += 1
    else:
        if first:
            firstL = l
            first = 0
        c += l//2
        l = 1
    olds = S[i]
    
    if i == len(S)-1:
        lastL = l
        c += l//2

if S[0] == S[-1] and firstL%2 == 1 and lastL%2 == 1:
    print((c+1)*K-1)
else:
    print(c*K)


### FIXED CODE ###

import sys

S = input()
K = int(input())

if len(S) == 1:
    print(K//2)
    sys.exit()
if len(S) == 2:
    if S[0] == S[1]:
        print(K)
    else:
        print('0')
    sys.exit()

olds = S[0]
l = 1
c = 0
first = 1
for i in range(1,len(S)):

    if olds == S[i]:
        l += 1
    else:
        if first:
            firstL = l
            first = 0
        c += l//2
        l = 1
    olds = S[i]
    
    if i == len(S)-1:
        if first:
            print(len(S)*K//2)
            sys.exit()
        lastL = l
        c += l//2

if S[0] == S[-1] and firstL%2 == 1 and lastL%2 == 1:
    print((c+1)*K-1)
else:
    print(c*K)
# -*- coding: utf-8 -*-
a = int(input())
judge = True
for i in range(a):
  b = int(input())
  if (b % 2 == 0) and ((b % 3 == 0) or (b % 5 == 0)):
    judge = False
# 出力
if judge:
  print("APPROVED")
else:
  print("DENIED")

### FIXED CODE ###

# -*- coding: utf-8 -*-
a = int(input())
lis = list(map(int, input().split()))
for i in range(a):
  judge = True
  if (lis[i] % 2 == 0):
    if (lis[i] % 3 != 0) and (lis[i] % 5 != 0):
      judge = False
      break
# 出力
if judge:
  print("APPROVED")
else:
  print("DENIED")
N, M = map(int, input().split())
G = [[] for i in range(M+1)]
for i in range(M):
    u, v = map(int, input().split())
    G[u].append(v)
s, t = map(int, input().split())

d = [-1] * (N + 1)

S = set()
S.add(s)
d[s] = 0
x = 1
while len(S) > 0:
    Q1 = set()
    for u in S:
        for v in G[u]:
            Q1.add(v)
    Q2 = set()
    for u in Q1:
        for v in G[u]:
            Q2.add(v)
    Q3 = set()
    for u in Q2:
        for v in G[u]:
            if d[v] < 0:
                d[v] = x
                Q3.add(v)
    x += 1
    S = Q3

print(d[t])


### FIXED CODE ###

N, M = map(int, input().split())
G = [[] for i in range(N+1)]
for i in range(M):
    u, v = map(int, input().split())
    G[u].append(v)
s, t = map(int, input().split())

d = [-1] * (N + 1)

S = set()
S.add(s)
d[s] = 0
x = 1
while len(S) > 0:
    Q1 = set()
    for u in S:
        for v in G[u]:
            Q1.add(v)
    Q2 = set()
    for u in Q1:
        for v in G[u]:
            Q2.add(v)
    Q3 = set()
    for u in Q2:
        for v in G[u]:
            if d[v] < 0:
                d[v] = x
                Q3.add(v)
    x += 1
    S = Q3

print(d[t])
nt(input())
A , B = map(int,input().split())

if A == B:
    if A % K == 0:
        print('OK')
    else:
        print('NG')

else:
    for i in range(B-A):
        i += A
        if i % K == 0:
            print('OK')
            break

    else:
        print('NG')


### FIXED CODE ###

K = int(input())
A , B = map(int,input().split())

if A == B:
    if A % K == 0:
        print('OK')

    elif B % K == 0:
        print('OK')

    else:
        print('NG')

else:
    for i in range(B-A+1):
        i += A
        if i % K == 0:
            print('OK')
            break

    else:
        print('NG')
a = list(map(int, input().split()))
L = list(map(int, input().split()))
d = 0
ans = 0
while d<=a[1]:
    d += L[ans]
    ans += 1
print(ans)

### FIXED CODE ###

a = list(map(int, input().split()))
L = list(map(int, input().split()))
d = 0
ans = 0
i=1
while i==1:
    d += L[ans]
    if d>a[1]:
        break
    ans += 1
    if ans==a[0]:
        break

print(ans+1)
N,K = map(int,input().split())
H = list(map(int,input().split()))
i = 0
count = 0
while sum(H[N-K]) == 0:
  while H[N-K] == 0:
    count += 1
    while i <= N-K:
      i += 1
print(count)

### FIXED CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))
H.sort(reverse=True)
 
sum = 0
for count in range(N):
        if count >= K:
            sum += H[count]
 
print(sum)
n,k = map(int,input().sprit())
if k == 1:
  print('0')
else:
  print(n-k)

### FIXED CODE ###

n,k = map(int,input().split())
if k == 1:
  print('0')
else:
  print(n-k)
md = 1000000007
n,m = map(int,input().split())

grid=[]
for i in range(n):
    grid.append(list(input()))

dp=[]
for i in range(m):
    dp.append([0]*m)
dp[0][0]=1
for i in range(1,n):
    if(grid[i][0]!="#"):
        dp[i][0]=dp[i-1][0]
    else:
        dp[i][0]=0

for j in range(1,m):
    if(grid[0][j]!="#"):
        dp[0][j]=dp[0][j-1]
    else:
        dp[0][j]=0

for i in range(1,n):
    for j in range(1,m):
        if(grid[i][j]=="#"):
            dp[i][j]=0
        else:
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%md
print(dp[n-1][m-1])


### FIXED CODE ###

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

grid=[]
for i in range(n):
    grid.append(list(input()))

dp=[]
for i in range(n):
    dp.append([0]*m)
dp[0][0]=1
for i in range(1,n):
    if(grid[i][0]!="#"):
        dp[i][0]=dp[i-1][0]
    else:
        dp[i][0]=0

for j in range(1,m):
    if(grid[0][j]!="#"):
        dp[0][j]=dp[0][j-1]
    else:
        dp[0][j]=0

for i in range(1,n):
    for j in range(1,m):
        if(grid[i][j]=="#"):
            dp[i][j]=0
        else:
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%md
print(dp[n-1][m-1])
n=int(input())
d=int(input())
cnt=0
for i in range(0,n):
  x=int(input())
  y=int(input())
  z=sqrt((x*x)+(y*y))
  if(z>=d):
    cnt+=1
    
print(cnt)

### FIXED CODE ###

import math
n, d = map(int, input().split()) 
cnt=0
for i in range(0,n):
  x, y = map(int, input().split()) 
  z=math.sqrt((x*x)+(y*y))
  if(z<=d):
    cnt+=1
    
print(cnt)
n = int(input())
h = list(map(int,input().split()))
count=0
sum=1
for(int i=1;i>=n;i++):
    for(int s=i-1;s>=0;s--):
      if h[i]>h[s]:
         count+=1
    if count==n:
       sum+=1
print(sum)

### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
sum = 1
for i in range(1,n):
  if max(h[:i])<=h[i]:
     sum+=1
print(sum)
import copy
import sys
sys.setrecursionlimit(10**7)

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def lcm(a, b):
    return (a // gcd(a, b)) * b

def main():
    n, m = map(int, input().split())
    # これだと72がREになる
    A = [int(x) for x in input().split()]
    # A_s = set(A)
    # A_ = copy.deepcopy(A)
    # a_lcm = A.pop()
    a_lcm = 1
    # Aの要素が複数ならlcmを計算する
    #if len(A) >= 1:
    for a in A:
        a_lcm = lcm(a_lcm, a)
    #else:
    #    a_lcm = a_lcm
    # 元のAの値とlcmの半分の値を割り切れるものがあったら0
    #for i in A_:
    for i in A:
        # if a_lcm / 2 % i == 0:
        if (a_lcm / i) % 2 == 0: 
            print(0)
            exit()
        # else:
        #     continue
    print(2)
    # # mがlcmの半分よりも小さかったら0
    # if (a_lcm / 2) > m:
    # # if a_lcm > m * 2:
    #     print(0)
    #     exit()
    # else:
    #     # # あとは定数倍の数調べて終わり
    #     ans = int((m - (a_lcm / 2)) // a_lcm) + 1
    #     print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import copy
# from math import gcd


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def lcm(a, b):
    return (a // gcd(a, b)) * b
def main():
    n, m = map(int, input().split())
    A = set([int(x) for x in input().split()])
    a_lcm = 1
    for a in A:
        a_lcm = lcm(a_lcm, a)
        # mがlcmの半分よりも小さかったら0
        if (a_lcm / 2) > m:
            print(0)
            exit()
    for a in A:
        if (a_lcm / 2) % a == 0:
            print(0)
            exit()
    # # あとは定数倍の数調べて終わり
    ans = int((m - (a_lcm / 2)) // a_lcm) + 1
    print(ans)

if __name__ == '__main__':
    main()
import sys
from bisect import *
input = sys.stdin.readline
N = int(input())
A = [0] + list(map(int, input().split()))
P = [[] for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(N+1):
        for k in range(N+1):
            P[i].append((A[i]+A[j]+A[k],j,k))
B = [-float("inf")]
res = []
for i in range(1,N+1):
    P[i].sort(key=lambda x:x[0])
    tmp = [p for p, _, _ in P[i]]
    k = bisect_left(tmp,B[-1])
    B.append(P[i][k][0])
    b,c = P[i][k][1], P[i][k][2]
    if b: res.append((b,i))
    if c: res.append((c,i))
print(len(res))
for b, i in res:
    print(b,i)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mi, ma = min(A), max(A)
print(2*N)
if abs(mi)<=ma:
    k = A.index(ma)
    print(k+1,1)
    print(k+1,1)
    for i in range(N-1):
        print(i+1,i+2)
        print(i+1,i+2)
else:
    k = A.index(mi)
    print(k+1,N)
    print(k+1,N)
    for i in reversed(range(N-1)):
        print(i+2,i+1)
        print(i+2,i+1)
x = input
print x*x*x

### FIXED CODE ###

x = input()
num = int(x)
print(num*num*num)
#!/usr/bin/env python
import numpy as np
N = int(input())
alphabets = 'abcdefghijklmnopqrstuvwxyz'
A = np.zeros((N, N))
for i in range(N):
    for j, c in enumerate(input()):
        A[i,j] = alphabets.index(c)

cnt = 0
for i in range(N):
    for j in range(N):
        B = np.roll(A, (i, j), (0, 1))
        if (B==B.T).all():
            cnt += 1
print(cnt)

### FIXED CODE ###

#!/usr/bin/env python
import numpy as np
N = int(input())
alphabets = list('abcdefghijklmnopqrstuvwxyz')
A = np.zeros((N, N), dtype=int)
for i in range(N):
    for j, c in enumerate(input()):
        A[i,j] = alphabets.index(c)

B = np.concatenate([A, A], axis=0)
cnt = 0
for i in range(N):
    C = B[i:i+N, :]
    if (C==C.T).all():
        cnt += 1
print(cnt*N)
ips = []
ips.append(input())
while True:
    try:
        ips.append(input())
    except (EOFError):
        break
num = int(ips[0])
hina = ips[1]
v = []
for i in range(num):
    if hina[i] not in v:
        v.append(hina[i])
if len(v) == 3:
    print("three")
elif len(v) == 4:
    print("four")

### FIXED CODE ###

a = int(input())
def more_than_three(a):
    if a < 3:
        return 0
    else:
        return a//3
print(more_than_three(a))
import bisect
I=lambda:map(int,input().split())
N,Q=I()
S=input()
m=[]
for i in range(N-1):
    if S[i]=='A' and S[i+1]=='C':
        m += [i]
#print(m)
for i in range(Q):
    l,r=I()
    li=bisect.bisect_left(m,l-1)
    ri=bisect.bisect_left(m,r-1)
    #print(i,li,ri)
    print(ri-li-1 if m[ri-1]==r else ri-li)

### FIXED CODE ###

I=lambda:map(int,input().split())
N,Q=I()
S=input()
m=[0]
for i in range(N-1):
    m+=[m[-1]+(1 if S[i:i+2]=='AC' else 0)]
#print(m)
for i in range(Q):
    l,r=I()
    print(m[r-1]-m[l-1])
mod = 10**9 + 7

def factorial(N,MOD,r=True):
    fact = [1]*(N+1)
    rfact = [1]*(N+1)
    r = 1
    for i in range(1,N+1):
        fact[i] = r = r * i % MOD
    rfact[N] = r = pow(fact[N],MOD-2,MOD)
    for i in range(N, 0, -1):
        rfact[i-1] = r = r * i % MOD
    if r:
        return fact,rfact
    else:
        return fact
fact,rfact = factorial(2*10**5,mod)
def perm(n,k): #上のfactorialと併用
    return fact[n]*rfact[n-k]%mod
def comb(n,k): #上のfactorialと併用
    return fact[n]*rfact[k]*rfact[n-k]%mod

n = int(input())
G = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)

euler = []
def dfs(pre,now):
    euler.append(now)
    for to in G[now]:
        if to == pre:
            continue
        dfs(now,to)
    euler.append(pre)

dfs(-1,0)

data = [[] for i in range(n)]
last = [-1]*n
for i,x in enumerate(euler[:-1]):
    if last[x] == -1:
        last[x] = i
        continue
    data[x].append((i-last[x])//2)
    last[x] = i

for i in range(n):
    if sum(data[i]) == n-1:
        continue
    data[i].append(n-1-sum(data[i]))

two = [1]
now = 1
for i in range(n):
    now *= 2
    now %= mod
    two.append(now)

ans = 0
for i in range(n):
    now = 1
    for x in data[i]:
        now += two[x]-1
        now %= mod
    ans += two[n-1]-now
    ans %= mod


ans *= pow(two[n],mod-2,mod)
ans %= mod

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n = int(input())
G = [[] for _ in range(n)]
mod = 10**9 + 7

for _ in range(n-1):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

stack = [0]
depth = [-1]*n
depth[0] = 0
while stack:
    v = stack.pop()
    d = depth[v]
    for nv in G[v]:
        if depth[nv] >= 0:continue
        depth[nv] = depth[v] + 1
        stack.append(nv)

d_to_i = [[] for _ in range(n)]

for i in range(n):
    d_to_i[depth[i]].append(i)

data = [[] for _ in range(n)]

for d in range(n-1,-1,-1):
    for v in d_to_i[d]:
        for nv in G[v]:
            if depth[nv] < depth[v]:continue
            if data[nv]:
                data[v].append(n-data[nv][-1])
        if data[v]:
            data[v].append(n-1-sum(data[v]))
        else:
            data[v].append(n-1)

ans = 0
two = [1]
for i in range(n):
    two.append(two[-1]*2%mod)
for i in range(n):
    now = two[n-1]-1
    for x in data[i]:
        now -= two[x]-1
        now %= mod
    ans += now

#print(ans)

x = two[n]
x = pow(x,mod-2,mod)
print(ans*x%mod)
A=int(input())
B=int(input())

if A <= 8 and B <= 8:
    print("Yay!")
else:
    print(":(")

### FIXED CODE ###

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

if A <= 8 and B <= 8:
    print("Yay!")
else:
    print(":(")
def main():
    input = input()
    if 0 <= input < 86400:
        hour = input / 3600
        minute = int((input // 60) % 60)
        seconde = int(input % 60)
        print("{0}:{1}:{2}".format(hour,minute,seconde))

if __name__ == "__main__":
    main()

### FIXED CODE ###

input = int(input())
if 0 <= input < 86400:
    hour = input / 3600
    minute = (input / 60) % 60
    second = input % 60
    print("%d:%d:%d" % (hour,minute,second))
x,y = map(int,input().split())
import sys

a = (2*x-y)/3
b = (2*y-x)/3
if not (a.is_integer() and  b.is_integer()):
    print(0)
    sys.exit()
a = int(a)
b = int(b)
from functools import reduce
def mycmb(n,r,p):
    r = min(r,n-r)
    if r == 0:
        return 1
    over = reduce(lambda x,y:x*y%p,range(n,n-r,-1))
    under = reduce(lambda x,y:x*y%p,range(1,r+1))
    return (over * pow(under,p-2,p))%p

mod = 10**9+7
print(mycmb(a+b,a,mod))


### FIXED CODE ###

x,y = map(int,input().split())
import sys
sys.setrecursionlimit(10**6)



a = (2*x-y)/3
b = (2*y-x)/3
if not (a.is_integer() and  b.is_integer()) or 2*x<y or 2*y<x:
    print(0)
    sys.exit()
    
a = int(a)
b = int(b)

from functools import reduce
def mycmb(n,r,p):
    r = min(r,n-r)
    if r == 0:
        return 1
    over = reduce(lambda x,y:x*y%p,range(n,n-r,-1))
    under = reduce(lambda x,y:x*y%p,range(1,r+1))
    return (over * pow(under,p-2,p))%p

mod = 10**9+7
print(mycmb(a+b,a,mod))
n = int(input())
a = map(int, input().split())

ans = -1
isEven = True

while isEven:
  list_tmp = []
  for an in a:
    if an % 2 ==0:
      list_tmp.append(an / 2)
    else:
      isEven = False
      break;
  a = list_tmp
  ans += 1

print(ans)


### FIXED CODE ###

print(input().count('1'))
for _ in range(int(input())):
    a,b,c,d,e,f,g,h=map(float, input().split())
    try:
        i = (b-d)/(a-c)
    except:
        i = 90

    try:
        j = (f-h)/(e-g)
    except:
        j = 90
    
    if i == j:
        print("Yes")
    else:
        print("No")

input()

### FIXED CODE ###

for _ in range(int(input())):
    a,b,c,d,e,f,g,h=map(float, input().split())
    
    if abs((c-a)*(h-f) - (g-e)*(d-b)) < 1e-10:
        print("YES")
    else:
        print("NO")
a = [int(i) for i in input().split()]~


output = max(a)

b = a.index(max(a))

a[b] = a[b] - 1

output = output + max(a)

print(output)


### FIXED CODE ###

a = [int(i) for i in input().split()]
output = max(a)

b = a.index(max(a))

a[b] = a[b] - 1

output = output + max(a)

print(output)
a=input()
b=a.next(a)
print(b)


### FIXED CODE ###

alp='abcdefghijklmnopqrstuvwxyz'
s=str(input())
flag=False
for c in alp:
  if flag:
    print(c)
    break
  if c==s:
    flag=True