Harryxun/stf_run huggingface dataset:
import sys

sys.setrecursionlimit(10**18)

def dfs(now, prev):
    ans[now]+=(h[now]+ans[prev])
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            if memo[next]==True:
                # 過去に訪れていれば終わらせる
                return False
            else:
                memo[next] = True
                dfs(next, now)


n, q = map(int, input().split())
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

h=[0]*n
for i in range(q):
    u, v = map(int, input().split())
    u -= 1
    h[u]+=v

ans=[0]*n
memo = [False for i in range(n)]
dfs(0,0)

print(' '.join(map(str, ans)))

### FIXED CODE ###

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

def dfs(now, prev):
    ans[now]+=(h[now]+ans[prev])
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            if memo[next]==True:
                # 過去に訪れていれば終わらせる
                return False
            else:
                memo[next] = True
                dfs(next, now)
 
#木構造の取り込み 
n, q = map(int, input().split())
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
 
#操作の取り込み
h=[0]*n
for i in range(q):
    u, v = map(int, input().split())
    u -= 1
    h[u]+=v
 
#初期のカウンター
ans=[0]*n
memo = [False for i in range(n)]
 
#DFSでカウンターを動かす
dfs(0,0)
 
print(' '.join(map(str, ans)))
num=raw_input('the 3 number of days:')
numberdays=num.split(' ')
if int(numberdays[2])-int(numberdays[1])>int(numberdays[0]):
    print 'dangerous'
if 0<int(numberdays[2])-int(numberdays[1])<=int(numberdays[0]):
    print 'safe'
if if int(numberdays[2])-int(numberdays[1])<=0:
    print 'delicious'

### FIXED CODE ###

num=raw_input('')
numberdays=num.split(' ')
if int(numberdays[2])-int(numberdays[1])>int(numberdays[0]):
    print 'dangerous'
if 0<int(numberdays[2])-int(numberdays[1])<=int(numberdays[0]):
    print 'safe'
if int(numberdays[2])-int(numberdays[1])<=0:
    print 'delicious'
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, a, b = MAP()

# x = n // (a + b)
# pr/int(x)
x = 0
x += (n // (a + b)) * a
x += (n % (a+b)) % b
print(x)

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, a, b = MAP()

# x = n // (a + b)
# pr/int(x)
x = 0
x = (n // (a + b)) * a
y = 0
if a != 0:
    y = n % (a+b)
    if not 0 <= y <= a:
        y = a

print(x + y)
n = int(input())
print(a+a**2+a**3)

### FIXED CODE ###

n = int(input())
print(n+n**2+n**3)
List = list(map(int, input().split()))
ans = 'YES'
for i in List:
  if(List[i] != List[i+1]):
    ans = 'NO'
    break
print(ans)

### FIXED CODE ###

n = int(input())
s = list(map(int,input().split()))
t = 0
for i in range(n):
  s.append(i)

for i in range(n):
  if(s[i] == i + 1):
    t += 0
  else:
    t += 1
if(t == 0 or t == 2):
  print('YES')
else:
  print('NO')
N,M = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]

class UnionFind:
    def __init__(self,N):
        self.root = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.root[a] == a:
            return a
        else:
            self.root[a] = self.root(self.root[a])
            return self.root[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.root[ra] = rb
        else:
            self.root[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

uf = UnionFind(N)
for x,y,z in src:
    x,y = x-1,y-1
    uf.unite(x,y)
print(N - uf.count)


### FIXED CODE ###

def find(x):
    if root[x] == x:
        return x
    else:
        root[x] = find(root[x])
        return root[x]

def same(x,y):
    return find(x) == find(y)

def unite(x,y):
    x = find(x)
    y = find(y)
    if rank[x] == rank[y]:
        root[y] = x
        rank[x] += 1
    elif rank[x] > rank[y]:
        root[y] = x
    elif rank[x] < rank[y]:
        root[x] = y
    
n,m = map(int, input().split())
root = [i for i in range(n)]
rank = [0 for i in range(n)]

for i in range(m):
    x, y, z = [int(i)-1 for i in input().split()]
    if not same(x,y):
        unite(x,y)
    
for i in range(n):
    find(i)

print(len(list(set(root))))
import sys

args = sys.argv

if (int(args[1]) * int(args[2])) % 2 is not 0:
    print('Odd')
else:
    print('Even')

### FIXED CODE ###

input_ = list(map(int, input().split()))

if (input_[0] * input_[1]) % 2 is not 0:
    print('Odd')
else:
    print('Even')
N = int(input())
c = str(input())

left = 0
right = 0
Wcount = 0
Rcount = 0
for i in range(len(c)):
    while c[left] != 'W':
        left += 1
    while c[len(c)-1-right] != 'R':
        right += 1
    if (left + right) >= len(c):
        break
    Wcount += 1
    Rcount += 1
    left += 1
    right += 1

print(Wcount)

### FIXED CODE ###

N = int(input())
c = str(input())

Rcount = 0
Wcount = 0
for i in range(len(c)):
    if c[i] == 'R':
        Rcount += 1
for i in range(Rcount):
    if c[i] == 'W':
        Wcount += 1

print(Wcount)
def dfs(s):
    if int(s) > N:
        return 0
    ret = 1 if all(s.count(c) > 0 for c in '753') else 0
    for c in '753':
        ret += dfs(s+c)
    return ret
print(dfs('0'))

### FIXED CODE ###

N = int(input())

def dfs(s):
    if int(s) > N:
        return 0
    ret = 1 if all(s.count(c) > 0 for c in '753') else 0
    for c in '753':
        ret += dfs(s+c)
    return ret
print(dfs('0'))
N = int(input())
L = list(map(int,input().split()))



ans = 0

for i in range(len(L)):
    for j in range(i+1,len(L)):
        for k in range(j+1,len(L)):
            #print("L[i]:",L[i],"L[j]:",L[j],"L[k]:",L[k])
            if L[i]+L[j] > L[k] and L[j]+L[k] > L[i] and L[k]+L[i] > L[j] and L[i] != L[j] and L[j] != L[k] and L[k] != L[i]:
                #print("L[i]:",L[i],"L[j]:",L[j],"L[k]:",L[k])
                ans += 1

prinr(ans)

### FIXED CODE ###

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



ans = 0

for i in range(len(L)):
    for j in range(i+1,len(L)):
        for k in range(j+1,len(L)):
            #print("L[i]:",L[i],"L[j]:",L[j],"L[k]:",L[k])
            if L[i]+L[j] > L[k] and L[j]+L[k] > L[i] and L[k]+L[i] > L[j] \
            and L[i] != L[j] and L[j] != L[k] and L[k] != L[i]:
                #print("L[i]:",L[i],"L[j]:",L[j],"L[k]:",L[k])
                ans += 1

print(ans)
# -*- coding: utf-8 -*-
"""
Spyder Editor

This is a temporary script file.
"""

#f = open("/Users/naoki/Documents/Atcoder/input.txt")
N = int(input())

A = list(map(int, input().split()))
A.insert(0, 0)

select_num = N//2
Dp = [[[-9999] *2] * (select_num+1)] * (N+1)

for i in range(1,N+1):
    Start = (i-1)//2
    End = (i+1)//2
    
    for j in range(Start,End+1):
        Dp[i][j][0] = max(Dp[i-1][j][1], Dp[i-1][j][0])
        # [0] in 3rd dimension  not chosen at last num
        # must be transfered from [i-1]
    for j in range(Start,End+1):
        if j == 1:
            Dp[i][j][1] = 0 + A[i]
        else:
            Dp[i][j][1] = Dp[i-1][j-1][0]+A[i]

print(max(Dp[-1][select_num][0], Dp[-1][select_num][1]))

### FIXED CODE ###


#f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")
N = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)

select_num = N//2
inf = -10e+100

Dp_f = [[inf] * (3) for _ in range(N+1)]
Dp_s = [[inf] * (3) for _ in range(N+1)]
# 3　次元はそれぞれStart~3つに該当

pre_margin = 0
for i in range(1,N+1):
    Start = (i-1)//2
    End = (i+1)//2
    
    cur_margin = Start
    
    for j in range(Start,End+1):
        Dp_f[i][j-cur_margin] = max(Dp_s[i-1][j-pre_margin], Dp_f[i-1][j-pre_margin])   
        # [0] in 3rd dimension  not chosen at last num
        # must be transfered from [i-1]
    for j in range(Start,End+1):
        if j-1 == 0:
            Dp_s[i][j-cur_margin] = 0 + A[i]
        else:
            Dp_s[i][j-cur_margin] = Dp_f[i-1][j-1-pre_margin]+A[i]
    
    pre_margin = cur_margin
print(max(Dp_f[-1][select_num - cur_margin], Dp_s[-1][select_num - cur_margin]))
N,D=map(int,input().split())
X=[]
Y=[]
for i in range(N):
    x,y=input().split()
    X.append(int(x))
    Y.append(int(y))

import math
def get_distance(x,y):
    d=math.sqrt(((x)**2+(y)**2))
    return d

a=0
for i in range(N+1):
    distance=get_distance(x=X[i],y=Y[i])
    if distance<=N:
        a+=1
print(a)

### FIXED CODE ###

N,D=map(int,input().split())
X=[]
Y=[]
for i in range(N):
    x,y=input().split()
    X.append(int(x))
    Y.append(int(y))

import math
def get_distance(x,y):
    d=math.sqrt(((x)**2+(y)**2))
    return d

a=0
for i in range(N):
    distance=get_distance(x=X[i],y=Y[i])
    if distance<=D:
        a+=1
print(a)
import sys
buf=sys.stdin.read()
n=int(buf[0])
h=list(map(int,buf[1].split()))

dp=[0 for i in range(n+1)]
dp[1]=h[0]
for i in range(2,n):
	dp[i+1]=min(dp[i]+abs(h[i]-h[i+11]),dp[i-1]+abs(h[i-1]-h[i+1]))
print(dp[n])

### FIXED CODE ###

def main():
    n = int(input())
    h = [int(i) for i in input().split()]
    ans = solve(n, h)
    print(ans)


def solve(n, h):
    dp =[0 for _ in range(n)]
    dp[1] = dp[0] + abs(h[1] - h[0])
    for i in range(1, n - 1):
        dp[i + 1] = min(dp[i] + abs(h[i + 1] - h[i]), dp[i - 1] + abs(h[i + 1] - h[i - 1]))
    return dp[n - 1]


if __name__ == '__main__':
    main()
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return r'\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m=map(int,input().split())
u=UnionFind(n)
ans=0
p=list(map(lambda x:int(x-1),input().split()))
for i in range(m):
  a,b=map(lambda x:x-1,map(int,input().split()))
  u.union(a,b)
for i in range(n):
  if u.same(i,p[i]):
    ans+=1
print(ans)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return r'\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m=map(int,input().split())
u=UnionFind(n)
ans=0
p=list(map(lambda x:int(x)-1,input().split()))
for i in range(m):
  a,b=map(lambda x:x-1,map(int,input().split()))
  u.union(a,b)
for i in range(n):
  if u.same(i,p[i]):
    ans+=1
print(ans)
n = int(input())
a = input()

a = a.split()

alice = 0
bob = 0
ans = 0

for i in range(n):
	a[i] = int(a[i])

a = a.reverse()

for i in range(n):
	if i%2 == 0:
		alice = alice + int(a[i])
	else:
		bob = bob + int(a[i])
	
print(alice - bob)

### FIXED CODE ###

n = int(input())
a = input()

a = a.split()


for i in range(n):
	a[i] = int(a[i])

a	= sorted(a)
a.reverse()

alice = a[0]
bob = 0
for i in range(1, n):
	if i%2 == 0:
		alice = alice + a[i]
	else:
		bob = bob + a[i]
	
print(alice - bob)
l = input().split(" ")
j = input().split(" ")
k = int(l[0])
n = int(l[1])
x = 0
for i in range(n):
  d = int(j[i+1]) - int(j[i])
  x = max(x,d)
dt = k - int(x)
print(dt)


### FIXED CODE ###

KN = input().split(' ')
K = int(KN[0])
N = int(KN[1])
M = K/2
Al = input().split(' ')
A = []

for home in Al:
  A.append(int(home))

m = A[0]+(K-A[-1])
 
for i in range(N-1):
  m = max(m,abs(A[i]-A[i+1]))

print(K-m)
from sys import exit
H, W, N = map(int, input().split())
sr, sc = map(int, input().split())
S = input()
T = input()
ul = 1
dl = H
rl = W
ll = 1
for s, t in zip(S[1::][::-1], T[::-1]):
    if t == 'U':
        dl = min(H, dl+1)
    elif t == 'D':
        ul = max(1, ul-1)
    elif t == 'L':
        rl = min(W, rl+1)
    else:
        ll = max(1, ll-1)
    if s == 'U':
        ul += 1
    elif s == 'D':
        dl -= 1
    elif s == 'L':
        ll += 1
    else:
        rl -= 1
    if ul > dl or ll > rl or ul == H + 1 or dl == 0 or ll == W + 1 or rl == 0:
        print('NO')
        exit()
s = S[0]
if s == 'U':
    ul -= 1
elif s == 'D':
    dl += 1
elif s == 'L':
    ll -= 1
else:
    rl += 1

if ul <= sr <= dl and ll <= sc <= rl:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
G = [input() for _ in range(H)]
dist = [0]*(H*W)
bn = 0
B = deque()
geta = W
for i, g in enumerate(G):
    for j, f in enumerate(g):
        if f == '#':
            bn += 1
            B.append(i*geta + j)
visited = set(B)
while bn < H*W:
    if not B:
        break
    dh, dw = divmod(B.pop(), geta)
    dhw = dh * geta + dw
    for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        ni, nj = dh + di, dw + dj
        if not (0 <= ni <= H - 1) or not (0 <= nj <= W - 1):
            continue
        nij = ni * geta + nj
        if nij in visited or G[ni][nj] == '#':
            continue
        visited.add(nij)
        dist[nij] = 1 + dist[dhw]
        B.appendleft(nij)
print(max(dist))
# -*- coding: utf-8 -*-
"""
Created on Sun Nov  4 21:46:51 2018

@author: sk
"""


a,b, c,d = map(int, input().split())

s1=a+b
s2=c+d

if s1>s2:
  print("Left")
elseif s1==s2:
  print("Balanced")
else:
  print("Right")





### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Nov  4 21:46:51 2018

@author: sk
"""


a,b,c,d = map(int, input().split())

s1=a+b
s2=c+d

if s1>s2:
  print("Left")
elif s1==s2:
  print("Balanced")
else:
  print("Right")
print(sum([s == t fot s, t in zip(input(), input())]))

### FIXED CODE ###

S = input()
T = input()

ans = 0

for s, t in zip(S, T):
    ans += s == t
print(ans)
n,k=map(int,input(),split())
if n%2==0:
    if n/2>=k:
        print('YES')
    else:
        print('NO')
else:
    if (n//2)+1>=k:
        print('YES')
    else:
        print('NO')

### FIXED CODE ###

n,k=map(int,input().split())
if n%2==0:
    if n/2>=k:
        print('YES')
    else:
        print('NO')
else:
    if (n//2)+1>=k:
        print('YES')
    else:
        print('NO')
# input
x, y, z, k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

import heapq


a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

index_hstr = []
deliciouses = []
# priority queue
pq = []
heapq.heappush(pq, (-a[0] - b[0] - c[0], 0, 0, 0))
index_hstr.append((0, 0, 0))

for t in range(k):
    deli, i, j, k = heapq.heappop(pq)
    if (i+1, j, k) not in index_hstr:
        heapq.heappush(pq, (-a[i+1] - b[j] - c[k], i+1, j, k))
        index_hstr.append((i+1, j, k))
    if (i, j+1, k) not in index_hstr:
        heapq.heappush(pq, (-a[i] - b[j+1] - c[k], i, j+1, k))
        index_hstr.append((i, j+1, k))
    if (i, j, k+1) not in index_hstr:
        heapq.heappush(pq, (-a[i] - b[j] - c[k+1], i, j, k+1))
        index_hstr.append((i, j, k+1))
    deliciouses.append(-deli)


pass


### FIXED CODE ###

# input
x, y, z, k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ab = []
ab.extend([i+j for j in b for i in a])
ab.sort(reverse=True)

abc = []
abc.extend([i+j for j in ab[:k] for i in c])
abc.sort(reverse=True)

print('\n'.join(str(i) for i in abc[:k]))
a = input()
b = input()
c = input()

l = list(a)
m = list(b)
n = list(c)
if len(l)>0:
    t = a.pop()
k = 'a'
while len(l) >0 and len(m) > 0 and len(n) > 0:
    k = t
    if t == 'a':
        t = l.pop()
    elif t == 'b':
        t = m.pop()
    elif t == 'c':
        t = n.pop()
print(k)

### FIXED CODE ###

s={i:list(input()) for i in "abc"}
x="a"
while s[x]:
    x=s[x].pop(0)
print(x.upper())
N = int(input())
mod = 10 **9 + 7

def equal(item0, item1, delta = 10 ** (-24)):
    if abs(item0 - item1) < delta:
        return True
    else:
        return False
def bigger(item0, item1, delta = 10** (-24)):
    if item0 -item1 > delta:
        return True
    else:
        return False

ab = []
ba = []
zero = 0
from bisect import insort
from math import gcd
for _ in range(N):
    A, B = map(int, input().split())
    if A*B == 0:
        if A == 0 and B == 0:
            zero += 1
        elif A == 0 and B != 0:
            ab = [0] + ab
        else:
            ba = [0] + ba
    elif A*B > 0:
        d = gcd(A,B)
        insort(ab, (A//d)/(B//d))
    else:
        insort(ba, -(B//d)/(A//d))
print(ab,ba)
def make_count(list):
    k = 0
    lis = []
    while k < len(list):
        cnt = 1
        while k+1 < len(list):
            if list[k] == list[k+1]:
                cnt += 1
                k += 1
                continue
            else:
                break
        lis.append([list[k], cnt])
        k += 1
    return lis

ab = make_count(ab)
ba = make_count(ba)
from collections import deque
ab = deque(ab)
ba = deque(ba)
ans = 1 #all pattern
flag = True
pair = []
if len(ab) == 0:
    print(pow(2, N-zero, mod)+zero-1)
    exit()
if len(ba) == 0:
    print(pow(2, N-zero, mod)+ zero -1)
    exit()


while True:
    if flag:
        a = ab.popleft()
        b = ba.popleft()
    flag = False
    if a[0] == b[0]:
        pair.append([a[1], b[1]])
        if ab:
            a = ab.popleft()
        else:
            a = [-1, 0]
        if ba:
            b = ba.popleft()
        else:
            b = [-1, 0]
        if a[0] == b[0] == -1:
            break
    elif a[0] >b[0]:
        if ba:
            pair.append([0,b[1]])
            b = ba.popleft()
            continue
        elif ab:
            pair.append([a[1],0])
            a = ab.popleft()
            b = [-1, 0]
            continue
        else:
            if a[0] != -1:
                pair.append([a[1], 0])
            if b[0]!= -1:
                pair.append([0, b[1]])
            break
    else:
        if ab:
            pair.append([a[1], 0])
            a = ab.popleft()
            continue
        elif ba:
            pair.append([0, b[1]])
            b = ba.popleft()
            a = [-1, 0]
        else:
            if a[0] != -1:
                pair.append([a[1], 0])
            if b[0]!= -1:
                pair.append([0, b[1]])
            break
ans = 1
for item in pair:
    ans *= pow(2, item[0], mod) + pow(2, item[1], mod) -1
    ans %= mod
ans += zero-1
ans %= mod
print(ans)




### FIXED CODE ###

from collections import defaultdict
from math import gcd
N = int(input())
MOD = 10**9 + 7
L = defaultdict(lambda: [0,0])
zero = 0
for _ in range(N):
    A, B = map(int, input().split())
    if A==0: d=B
    elif B==0: d=A
    else: d=gcd(A,B)
    if d != 0:
        A, B = A//d, B//d
        if A<0: A, B = -A, -B
        if B>0: L[(A,B)][0] += 1
        else: L[(-B,A)][1] += 1
    else: zero += 1

res = 1

for x,y in L.values():
    res *= pow(2,x,MOD) + pow(2,y,MOD) -1
    res %= MOD
print((res+zero-1)%MOD)
import numpy as np
from math import factorial
MOD = 10**9 + 7

n = int(input())
X = list(map(int, input().split()))
dist = np.diff(X)

L = np.array([1 / x for x in range(1, n)])

L = np.cumsum(L)
n_1 = factorial(n-1)
L *= n_1

print(int(np.sum(L * dist) % MOD))


### FIXED CODE ###

import numpy as np
from math import factorial
MOD = 10**9 + 7

n = int(input())

dist = np.diff(list(map(int, input().split())))
L = np.cumsum(np.array([1 / x for x in range(1, n)]))
n_1 = factorial(n-1) % MOD

# fac = [1] * n
# for i in range(1,n):
# 	fac[i] = fac[i-1] * i % MOD

# print(int(np.sum(L * dist * n_1)) % MOD)
# ans = 0
# for l, d in zip(L, dist):
#     print("l d ", l * d)
#     ans += l * d
#     ans %= MOD

ans = 0
tmp = 0
for i, d in enumerate(dist):
    tmp += pow(i+1, MOD-2, MOD)
    ans += tmp * d
    ans %= MOD

# print(n_1)
print(ans * n_1 % MOD)
# print(int(np.sum(dist * L * n_1) % MOD))
n = int(input())
a_list = [int(x) for x in input().split()]

if 0 in a_list:
  print(0)
  

else:
  flg = True
  num = 1
  for a in a_list:
    num *= a
    if num > 1E18:
      print(-1)
      flg = False
      break

if flg:
  print(num)

### FIXED CODE ###

n = int(input())
a_list = [int(x) for x in input().split()]

if 0 in a_list:
  print(0)
  
else:
  flg = True
  num = 1
  for a in a_list:
    num *= a
    if num > 1E18:
      print(-1)
      flg = False
      break

  if flg:
    print(num)