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

def solve(a_s) -> int:
  def get_ret_from_xs(xs) -> int:
    ret = 0
    for i, x in enumerate(xs):
      ret += 2**i * (x % 2)
      ret %= 10**9 + 7
    return ret

  # zeros = [1, 1] + [0] * 58  # 各要素 0 ~ n. 要素iは、下 i +1 桁目が0である A_? の個数
  # ones = [2, 2] + [0] * 58 # 各要素 0 ~ n. 要素iは、下 i +1 桁目が0である A_? の個数
  zeros = [0] * 60
  ones = [0] * 60

  for a in a_s:
    for i in range(len(zeros)):
      a_bin = format(a, '060b')
      a_i_digit_from_right = a_bin[60 - i - 1]
      if a_i_digit_from_right == '0':
        zeros[i] += 1
      else:
        ones[i] += 1

  # 繰り上がりのせいで、xsの要素数は60を超えることがあるので注意
  xs = []
  i = 0
  while True:
    x_i = 0
    if i <= 59:
      x_i = (zeros[i] * ones[i])
    if i >= 1:
      x_i += xs[i - 1] // 2
    xs.append(x_i)

    if i >= 60 and x_i // 2 == 0:
      break

    i += 1

  #xs = [2, 3, 1]
  return get_ret_from_xs(xs)


n = int(input().strip())
a_s = [int(s) for s in input().split()]

#a_s = [1, 2, 3]
#a_s = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
#a_s = [3, 14, 159, 2653, 58979, 323846, 2643383, 27950288, 419716939, 9375105820]

print(solve(a_s))


### FIXED CODE ###

def solve(a_s) -> int:
  # def get_ret_from_xs(xs) -> int:
  #   # 繰り上がり処理ありバージョン
  #   ret = 0
  #   for i, x in enumerate(xs):
  #     ret += 2**i * (x % 2)
  #     ret %= 10**9 + 7
  #   return ret
  #
  # def get_ret_from_xs2(xs) -> int:
  #   ret = 0
  #   for i, x in enumerate(xs):
  #     ret += 2**i * x
  #     ret %= 10**9 + 7
  #   return ret

  # zeros = [1, 1] + [0] * 58  # 各要素 0 ~ n. 要素iは、下 i +1 桁目が0である A_? の個数
  # ones = [2, 2] + [0] * 58 # 各要素 0 ~ n. 要素iは、下 i +1 桁目が0である A_? の個数
  zeros = [0] * 60

  ret = 0
  for i in range(60):
    ones = sum([(a >> i) & 0b1 for a in a_s])
    ret += 2**i * (ones * (len(a_s) - ones))
    ret %= 10**9 + 7
  return ret

  # for a in a_s:
  #   for i in range(len(zeros)):
  #     # a_bin = format(a, '060b')
  #     # a_i_digit_from_right = a_bin[60 - i - 1]
  #     # if a_i_digit_from_right == '0':
  #     #   zeros[i] += 1
  #     # else:
  #     #   ones[i] += 1
  #
  #     a_i_digit_from_right = (a >> i) & 0b1
  #     if a_i_digit_from_right == 0:
  #       zeros[i] += 1
  #
  # # 繰り上がり処理しないでも、各桁で収めてもいいんだ！
  # xs = [zeros[i] * (len(a_s) - zeros[i]) for i in range(60)]
  # return get_ret_from_xs2(xs)
  #
  #
  # # # 繰り上がりのせいで、xsの要素数は60を超えることがあるので注意
  # # xs = []
  # # i = 0
  # # while True:
  # #   x_i = 0
  # #   if i <= 59:
  # #     x_i = (zeros[i] * ones[i])
  # #   if i >= 1:
  # #     x_i += xs[i - 1] // 2
  # #   xs.append(x_i)
  # #
  # #   if i >= 60 and x_i // 2 == 0:
  # #     break
  # #
  # #   i += 1
  #
  # #xs = [2, 3, 1]
  # #return get_ret_from_xs(xs)


n = int(input().strip())
a_s = [int(s) for s in input().split()]

#a_s = [1, 2, 3]
#a_s = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
#a_s = [3, 14, 159, 2653, 58979, 323846, 2643383, 27950288, 419716939, 9375105820]

print(solve(a_s))
### BUGGY CODE ###

n = int(input())
l = []
for i in range(n):
    com = input().split()
    if com[0] == "insert":
        key = int(com[1]) 
        l.insert(0, key)
    elif com[0] == "delete":
        key = int(com[1]) 
        if int(key) in l:
            l.remove(key)
    elif com[0] == "deleteFirst":
        del l[0]
    else:
        del l[-1]
print(*l)

### FIXED CODE ###

import sys
from collections import deque
 
n = int(sys.stdin.readline())
que = deque()
for i in range(n):
    line = sys.stdin.readline()
    op = line.rstrip().split()
    if "insert" == op[0]:
        que.appendleft(op[1])
    elif "delete" == op[0]:
        if op[1] in que:
            que.remove(op[1])
    elif "deleteFirst" == op[0]:
        que.popleft()
    else:
        que.pop()
 
print(*que)
### BUGGY CODE ###

sList, tList = map(list, sorted([input(), input()], key=lambda x: len(x)))

dp = [[""] * (len(tList) + 1) for _ in range(2)]
index = 0
for i, s in enumerate(sList, start=1):
    index = i % 2
    sameStr = ""
    for j, t in enumerate(tList, start=1):
        aboveStr = dp[index-1][j]
        if s == t:
            sameStr = dp[index-1][j-1] + s
        dp[index][j] = sameStr if len(sameStr) > len(aboveStr) else aboveStr

print(dp[index][-1])



### FIXED CODE ###

sList, tList = list(input()), list(input())

dp = [[0] * (len(tList) + 1) for _ in range(len(sList) + 1)]
for i, s in enumerate(sList, start=1):
    sameNum = 0
    for j, t in enumerate(tList, start=1):
        num = dp[i-1][j]
        if s == t:
            sameNum = max(num, dp[i-1][j-1] + 1)
        dp[i][j] = max(num, sameNum)

ans = ""

while(i > 0, j > 0):
    num = dp[i][j]
    if num == 0:
        break
    if sList[i-1] == tList[j-1]:
        ans = sList[i-1] + ans
        i -= 1
        j -= 1
    else:
        if dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1

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

# coding: utf-8
# Your code here!

x,y,a,b,c = map(int,input().split())
p_a = list(map(int,input().split()))
p_b = list(map(int,input().split()))
p_c = list(map(int,input().split()))
p_a.sort(reverse=True)
p_b.sort(reverse=True)
p_c.sort(reverse=True)
p_c += [0]

ans = p_a[:x] + p_b[:y]
ans.sort(reverse=True)

while True:
    if ans[-1] > p_c[0]:
        break
    else:
        ans[-1] = p_c[0]
        p_c.pop(0)
        ans.sort(reverse=True)
print(sum(ans))

### FIXED CODE ###

x,y,a,b,c = map(int,input().split())
p_a = list(map(int,input().split()))
p_b = list(map(int,input().split()))
p_c = list(map(int,input().split()))
p_a.sort(reverse=True)
p_b.sort(reverse=True)
#p_c.sort(reverse=True)

ans = p_a[:x] + p_b[:y] + p_c
ans.sort(reverse=True)
print(sum(ans[:x+y]))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    G = [[] for _ in range(N)]
    for i in range(N-1):
        u, v, w = (int(i) for i in input().split())
        G[u-1].append((v-1,w))
        G[v-1].append((u-1,w))
    color = [-1] * N
    todo = []
    todo_append = todo.append
    todo_pop = todo.pop
    color[0] = 0
    todo_append(0)
    while todo:
        u = todo[-1]
        for next_v,w in G[u]:
            if color[next_v] != -1: 
                continue
            if w&1:
                color[next_v] = (color[u] + 1) % 2
            else:
                color[next_v] = color[u]
            todo_append(next_v)
            break
        else:
            todo_pop(-1)
    for c in color:
        print(c)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    G = [[] for _ in range(N+1)]
    st = 0
    st_w = 0
    for i in range(N-1):
        u, v, w = (int(i) for i in input().split())
        G[u].append((v, w))
        G[v].append((u, w))
        if i == 0:
            st = u
            st_w = w
    color = [-1] * (N+1)  # 0: white, 1: black, -1: undefined
    from collections import deque

    def coloring(v, w):
        """
        breadth-first search
        a simplified version
        """
        que = deque()
        color[v] = 0
        que.append((v, w))
        while que:
            u, w = que.popleft()
            for v, d in G[u]:
                if color[v] != -1:
                    continue
                if d % 2 != 0:
                    n_col = (color[u] + 1) % 2
                else:
                    n_col = color[u]
                color[v] = n_col
                que.append((v, d))

    coloring(st, st_w)
    for c in color[1:]:
        print(c)


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

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

def f(v, vs):
    kminmax = rkoma = fff = ffmx = 0
    for u in d[v]:
        if u in vs:
            continue
        vs.add(u)
        k1, koma, ff = f(u, vs)
        if k1 > kminmax:
            kminmax, ffmx = k1, ff
        rkoma += koma
        fff += ff
    r1 = kminmax+ffmx-fff if kminmax > fff - ffmx else fff % 2
    rkoma += km[v]
    return r1+rkoma, rkoma, fff+rkoma

N = int(input())
km = [0] + [int(i) for i in str(input().strip())]
d = [set() for _ in range(N+1)]
for _ in range(N-1):
    x, y = map(int, input().split())
    d[x].add(y)
    d[y].add(x)
r = 10**10
for i in range(N):
    a, c, fff = f(i+1, {i+1})
    if a == c:
        r = min((fff-c)//2, r)
print(r if r != 10**10 else -1)

### FIXED CODE ###

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

def f(v, vs):
    kminmax = 0
    r = 0
    rkoma = 0
    fff = 0
    ffmx = 0
    for u in d[v]:
        if u in vs:
            continue
        vs.add(u)
        k1, koma, ff = f(u, vs)
        if k1 > kminmax:
            kminmax = k1
            ffmx = ff
        kminmax = max(kminmax, k1)
        rkoma += koma
        fff += ff
    if kminmax > fff - ffmx:
        r1 = kminmax+ffmx-fff
    else:
        r1 = fff % 2
    rkoma += km[v]
#    print(v, r1 + rkoma, rkoma, fff + rkoma)
    return r1 + rkoma, rkoma, fff + rkoma

N = int(input())
km = [0] + [int(i) for i in str(input().strip())]
d = [set() for _ in range(N+1)]
for _ in range(N-1):
    x, y = map(int, input().split())
    d[x].add(y)
    d[y].add(x)

r = 10**10
#print(f(4, {4}))
for i in range(N):
    a, c, fff = f(i+1, {i+1})
#    print(i, a, c)
    if a == c:
        r = min(r, (fff-c)//2)
print(r if r != 10**10 else -1)
### BUGGY CODE ###

def solve_145e():
    from collections import namedtuple
    from operator import attrgetter
    import sys
    input = sys.stdin.readline

    Food = namedtuple('Food', 'time_to_eat deliciousness')

    N, T = map(int, input().split())
    foods = []
    for _ in range(N):
        row = map(int, input().split())
        foods.append(Food(*row))
    foods.sort(key=attrgetter('time_to_eat'))
    # 同じ料理の組を食べるなら時間のかかるものを後回しにしても結果は悪くならない

    dp = [-1] * T
    dp[0] = 0
    # dp[time]:=timeに食べ終わる注文の仕方で得られる最大満足度

    ma = 0  # 回答候補
    ca = 0  # フィニッシュ前候補
    for food in foods:
        # これでフィニッシュの場合
        ma = max(ma, ca + food.deliciousness)

        # まだ食べる場合
        for time in range(T - 1 - food.time_to_eat, -1, -1):
            if ~dp[time]:
                when_eat = dp[time] + food.deliciousness
                if dp[time + food.time_to_eat] < when_eat:
                    dp[time + food.time_to_eat] = when_eat
                    ca = max(ca, when_eat)

    print(ma)
    return


if __name__ == '__main__':
    solve_145e()


### FIXED CODE ###

def solve():
    from collections import namedtuple
    import sys

    input = sys.stdin.readline
    Dish = namedtuple('Dish', 'idx cost pt')

    n, t = map(int, input().split())
    dishes = []
    for idx in range(1, n + 1):
        cost, pt = map(int, input().split())
        dishes.append(Dish(idx=idx, cost=cost, pt=pt))

    dp_ht = [[0] * t for _ in range(n + 2)]  # head->tail
    dp_th = [[0] * t for _ in range(n + 2)]  # tail->head
    # dp[注文可能な範囲の端][完食にかかる総時間]:= 美味しさの最大値

    for dish in dishes:
        for cost_ in range(t):
            if cost_ >= dish.cost:
                dp_ht[dish.idx][cost_] = max(dp_ht[dish.idx - 1][cost_],
                                             dp_ht[dish.idx - 1][cost_ - dish.cost] + dish.pt)
            else:
                dp_ht[dish.idx][cost_] = dp_ht[dish.idx - 1][cost_]

    for dish in reversed(dishes):
        for cost_ in range(t):
            if cost_ >= dish.cost:
                dp_th[dish.idx][cost_] = max(dp_th[dish.idx + 1][cost_],
                                             dp_th[dish.idx + 1][cost_ - dish.cost] + dish.pt)
            else:
                dp_th[dish.idx][cost_] = dp_th[dish.idx + 1][cost_]

    ret = 0
    for last_dish in dishes:
        for cost_ in range(t):
            ret = max(ret, dp_ht[last_dish.idx - 1][cost_] + dp_th[last_dish.idx + 1][t - 1 - cost_] + last_dish.pt)
    return ret


print(solve())
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
BC=[input() for __ in range(M)]

for bc in BC:
    b,c=map(int,bc.split())
    A.extend(list([c]*b))
    A.sort(reverse=True)
    A=A[:N]

print(sum(A))


### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
BC=[list(map(int,input().split())) for __ in range(M)]
BC.sort(key=lambda x: x[1],reverse=True)

l=[]
for b,c in BC:
    if len(l)+b>N:
        l.extend(list([c]*b))
        break
    else:
        l.extend(list([c]*b))
A.extend(l)
A.sort(reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

n, m = map(int,input().split())
a = [sorted(map(int,input().split())) for _ in range(m)]
for i in range(n):
    if [1,i] in a and [i,n] in a:
        print("POSSIBLE")
        exit()
print(("IMPOSSIBLE"))

### FIXED CODE ###

n, m = map(int,input().split())
a = [[] for _ in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    a[x-1] += [y-1]
for i in a[0]:
    for j in a[i]:
        if j == n-1 :
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

N,K=list(map(int,input().split()))
dp_list=[10**10]*N
h=list(map(int,input().split()))
dp_list[0]=0
for i in range(N):
    for j in range(1,K+1):
        j=i+j
        if j<N:
            # if dp_list[j] is None:dp_list[j]=abs(h[j]-h[i])+dp_list[i]
            dp_list[j]=min(dp_list[j],abs(h[j]-h[i])+dp_list[i])
print(dp_list[-1])



### FIXED CODE ###

import numpy as np
N,K=list(map(int,input().split()))
dp_list=np.full(N,10**10,dtype=int)
h=list(map(int,input().split()))
h=np.array(h)
dp_list[0]=0
for i in range(1,N):
        dp_list[i:i+K] = np.fmin(dp_list[i:i+K], dp_list[i-1] + np.abs(h[i:i+K] - h[i-1]))
print(dp_list[-1])
### BUGGY CODE ###

def luka(n):
  if n==0:
    return 2
  if n==1:
    return 1
  return luka(n-1)+luka(n-2)

n = int(input())
print(luka(n))


### FIXED CODE ###

def luka(n):
  global lk
  if n==0:
    return 2
  if n==1:
    return 1
  if lk[n] != -1:
    return lk[n]
  lk[n] = luka(n-1)+luka(n-2)
  return lk[n]

lk = [-1]*100
n = int(input())
print(luka(n))
### BUGGY CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 998244353
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, K = LI()
    LR = [LI() for _ in range(K)]

    # N * KのDP?
    dp = [0] * N
    dp[0] = 1
    for i in range(N):
        for l, r in LR:
            for j in range(i + l, min(i + r + 1, N)):
                dp[j] += dp[i]
                dp[j] %= MOD

    print(dp[-1])

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 998244353
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, K = LI()
    LR = [LI() for _ in range(K)]

    dp = [0] * (N + 1)
    dp[0] = 1
    a = [0] * (N + 1)
    a[0] = 1
    a[1] = -1
    for i in range(N):
        for l, r in LR:
            left = min(i + l, N)
            right = min(i + r + 1, N)
            a[left] += dp[i]
            a[right] -= dp[i]
        dp[i+1] += dp[i] + a[i+1]
        dp[i+1] %= MOD
        # print(a)
        # print(dp)

    print(dp[-2])

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

S = input()

dp = [0] * 2019
ans = 0
for c in S:
    c = int(c)
    dp2 = [0] * 2019
    dp2[c] = 1
    for i in range(2019):
        if dp[i] == 0: continue
        dp2[(i*10+c)%2019] += dp[i]
    dp = dp2
    ans += dp[0]
print(ans)

### FIXED CODE ###

S = input()
r = 1
arr = [0]
for c in S[::-1]:
    arr.append((arr[-1] + int(c) * r) % 2019)
    r *= 10
    r %= 2019
from collections import Counter
ctr = Counter(arr)
ans = 0
for v in ctr.values():
    ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

N = int(input())  
A = [int(i) for i in input().split()] 
B=[0]*N
ans=0
for i in range(N):
    B[i]=(A.index(i+1)+1)
print(' '.join(map(str, B)))

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()] 
A.insert(0, 0)
B = [0]*N
mydict={}
for i in range(1,N+1):
    mydict[A[i]]=i
sorted(mydict.items(), key=lambda x: x[1])
for i in range(1,N+1):
    B[i-1]=mydict[i]
print(' '.join(map(str, B)))
### BUGGY CODE ###

S = input()
p = 10 ** 9 + 7
DP = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
DP[0][0] = 1
for i, s in enumerate(S[::-1]):
  if s == '?':
    for j in range(10):
      m = j * 10 ** i % 13
      for k in range(13):
        DP[i + 1][(k + m) % 13] += DP[i][k]
  else:
    m = int(s) * 10 ** i % 13
    for k in range(13):
      DP[i + 1][(k + m) % 13] += DP[i][k]
  for k in range(13):
    DP[i + 1][k] %= p
print(DP[-1][5])

### FIXED CODE ###

S = input()
p = 10 ** 9 + 7
DP = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
DP[0][0] = 1
M = [[0 for _ in range(13)] for _ in range(6)]
for i in range(6):
  for j in range(10):
    M[i][j] = j * 10 ** i % 13
for i, s in enumerate(S[::-1]):
  if s == '?':
    for j in range(10):
      m = M[i % 6][j]
      for k in range(13):
        DP[i + 1][(k + m) % 13] += DP[i][k]
  else:
    m = M[i % 6][int(s)]
    for k in range(13):
      DP[i + 1][(k + m) % 13] += DP[i][k]
  for k in range(13):
    DP[i + 1][k] %= p
print(DP[-1][5])
### BUGGY CODE ###

from operator import itemgetter

def main():
    N,M = list(map(int, input().split()))
    lst = []
    anslst = []
    for i in range(M):
        P,Y = list(map(int, input().split()))
        lst.append({'city_id':i, 'pref':P, 'year':Y})
    lst = sorted(lst, key = itemgetter('year'))
    for i in range(N):
        tmp = [ d for d in lst if d['pref'] == i+1]
        for j in range(len(tmp)):
            city_id = tmp[j]['city_id']
            pref = tmp[j]['pref']
            year = tmp[j]['year']
            id = '{0:06d}'.format(pref) + '{0:06d}'.format(j+1)
            anslst.append({'city_id':city_id, 'pref':pref, 'year':year, 'id':id})
    anslst = sorted(anslst, key = itemgetter('city_id'))
    for i in range(len(anslst)):
        print(anslst[i]['id'])

if __name__ == '__main__':
    main()


### FIXED CODE ###

from operator import itemgetter

def main():
    N,M = list(map(int, input().split()))
    lst = [[] for i in range(N)]
    anslst = []

    for i in range(M):
        P,Y = list(map(int, input().split()))
        lst[P-1].append({'city_id':i, 'pref':P, 'year':Y})

    for i in range(N):
        tmp = lst[i]
        tmp = sorted(tmp, key = itemgetter('year'))
        for j in range(len(tmp)):
            city_id = tmp[j]['city_id']
            pref = tmp[j]['pref']
            year = tmp[j]['year']
            id = '{0:06d}'.format(pref) + '{0:06d}'.format(j+1)
            anslst.append({'city_id':city_id, 'pref':pref, 'year':year, 'id':id})

    anslst = sorted(anslst, key = itemgetter('city_id'))
    for i in range(len(anslst)):
        print(anslst[i]['id'])

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

N=int(input())
E=[[] for _ in range(N)]
for _ in range(N-1):
    A,B=map(int,input().split())
    E[A-1].append(B-1)
    E[B-1].append(A-1)
MOD=10**9+7

#dp=子ノードの数+1(自分)
dp=[1]*N

root=0
parent=[0]*N
order=[]
def dfs():
    parent[root]=root
    stack=[root]
    while stack:
        node=stack.pop()
        order.append(node)
        for ss in E[node]:
            if parent[node]!=ss:
                stack.append(ss)
                parent[ss]=node

def solve():
    ans=0
    inv2=pow(2,MOD-2,MOD)
    #p0=すべての部分木に黒頂点が1つも含まれない確率
    p0=pow((1<<(N-1))%MOD,MOD-2,MOD)
    for i in reversed(order):
        if root!=i:
            dp[parent[i]]+=dp[i]
        p=0
        if len(E[i])>=2:
            #p0*(p1-1)=どれか1つの各部分木に黒頂点が1つ以上含まれる確率
            p1=1
            for s in E[i]:
                size=0
                if parent[i]!=s:
                    size=dp[s]
                elif i!=root:
                    size=N-dp[i]
                else:
                    continue
                p1+=(1<<size)-1
                p1%=MOD
            p=1-(p0*p1)
            p%=MOD
        ans+=p
        ans%=MOD
    #頂点iが白の確率
    ans=ans*inv2%MOD
    print(ans)

dfs()
solve()


### FIXED CODE ###

N=int(input())
E=[[] for _ in range(N)]
for _ in range(N-1):
    A,B=map(int,input().split())
    E[A-1].append(B-1)
    E[B-1].append(A-1)
MOD=10**9+7

#dp=子ノードの数+1(自分)
dp=[1]*N

root=0
parent=[0]*N
order=[]
def dfs():
    parent[root]=root
    stack=[root]
    while stack:
        node=stack.pop()
        order.append(node)
        for ss in E[node]:
            if parent[node]!=ss:
                stack.append(ss)
                parent[ss]=node

pow2=[1]*(N+1)
for i in range(1,len(pow2)):
    pow2[i]=pow2[i-1]*2%MOD

def solve():
    ans=0
    inv2=pow(2,MOD-2,MOD)
    #p0=すべての部分木に黒頂点が1つも含まれない確率
    p0=pow(pow2[N-1],MOD-2,MOD)
    for i in reversed(order):
        if root!=i:
            dp[parent[i]]+=dp[i]
        p=0
        if len(E[i])>=2:
            #p0*(p1-1)=どれか1つの各部分木に黒頂点が1つ以上含まれる確率
            p1=1
            for s in E[i]:
                size=0
                if parent[i]!=s:
                    size=dp[s]
                elif i!=root:
                    size=N-dp[i]
                else:
                    continue
                p1+=pow2[size]-1
            p=1-(p0*p1)
            p%=MOD
        ans+=p
        ans%=MOD
    #頂点iが白の確率
    ans=ans*inv2%MOD
    print(ans)

dfs()
solve()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = [0]
t = 0
for i in range(N):
    B.append(B[i] + A[i])

C = set(B)
for j in C:
    z = B.count(j)
    if z > 1:
        t += z*(z-1)/2

print(int(t))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = {}
t = 0
x = 0
B[0] = 1
for i in A:
    x += i
    t += B.get(x, 0)
    B[x] = B.get(x, 0) + 1

print(t)