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

H, N, *AB = map(int, open(0).read().split())
magics = [(A, B) for A, B in zip(*[iter(AB)] * 2)]
dp = [float("inf")] * (H + 1)
dp[0] = 0
for i in range(N):
    A, B = magics[i]
    for h in range(H):
        dp[min(h + A, H)] = min(dp[min(h + A, H)], dp[h] + B)
print(dp[-1])


### FIXED CODE ###

H, N, *AB = map(int, open(0).read().split())
A = []
B = []
for a, b in zip(*[iter(AB)] * 2):
    A.append(a)
    B.append(b)

dp = [float("inf")] * (H + 1)
dp[0] = 0

for i in range(N):
    for h in range(H):
        dec_health = min(h + A[i], H)
        dp[dec_health] = min(dp[dec_health], dp[h] + B[i])
print(dp[-1])
### BUGGY CODE ###

N = int(input())
num = 1
for _ in range(N):
  x, y = map(int, input().split())
  sum_xy = x+y
  while True:
    if num%sum_xy == 0:
      break
    else:
      num += num%sum_xy
print(num)


### FIXED CODE ###

import math

N = int(input())
x, y = map(int, input().split())
for _ in range(N-1):
  a, b = map(int, input().split())
  # n = max(math.ceil(x/a), math.ceil(y/b))
  na = nb = 0
  if x%a == 0:
    na = x//a
  else:
    na = x//a+1
  if y%b == 0:
    nb = y//b
  else:
    nb = y//b+1
  n = max(na, nb)
  x, y = n*a, n*b
print(x+y)
### BUGGY CODE ###

n = int(raw_input())


N = []
for i in range(1,n+1):
	N.append(i)

N2 = 1
for N1 in N:
	N2 = N2 * N1

a = 10**9+7
N2 = N2%a

print N2



### FIXED CODE ###

n = int(raw_input())


N = []
for i in range(1,n+1):
	N.append(i)

N2 = 1
for N1 in N:
	N2 = N2 * N1%(10**9+7)

print N2
### BUGGY CODE ###

n = int(input())
a = [0] + [int(input()) for i in range(n)]

end = {}

end[1] = True
to = a[1]

cnt = 0
while True:
    cnt += 1
    if to == 2:
        print(cnt)
        __import__("sys").exit()
    if end.get(to) == None:
        to = a[to]
    else:
        break

print(-1)


### FIXED CODE ###

n = int(input())
a = [0] + [int(input()) for i in range(n)]

end = {}

end[1] = True
to = a[1]

cnt = 0
while True:
    cnt += 1
    if to == 2:
        print(cnt)
        __import__("sys").exit()
    if end.get(to) == None:
        end[to] = True
        to = a[to]
    else:
        break

print(-1)
### BUGGY CODE ###

N,M=map(int, input().split())
wa={}
ac=[]
key=[]

    
for i in range(M):
    p,s=input().split()
    if p not in ac:
        if p not in key:
            key.append(p)
            wa[p]=0

        if s=="WA":
            wa[p]+=1
        else:
            ac.append(p)
ans=0
for i in key:
    if i in ac:
        ans+=wa[i]
print(len(ac),ans)




### FIXED CODE ###

N,M=map(int,input().split())
AC={}
WA={}
for i in range(M):
    a,b=input().split()
    if not(a in AC.keys()):
        if b=="AC":
            AC[a]=1
        else:
            if a in WA.keys():
                WA[a]+=1
            else:
                WA[a]=1
y=0
for i in AC.keys():
    if i in WA.keys():
        y+=WA[i]
print(sum(AC.values()),y)
### BUGGY CODE ###


N,M=map(int,input().split())

result=0
LR=[]
for i in range(M):
        LR.append(input().split())

for i in range(N+1):#0からNまで
    counter=0
    for j in LR:#['1','1']
        #print(j)

        L=int(j[0])
        R=int(j[1])
        if i<L or R<i:
            break
        if L<=i and i<=R:
            counter+=1

    if counter==M:
        result+=1
print(result)


### FIXED CODE ###


N,M=map(int,input().split())#ID,ゲート


LR=[]
for i in range(M):
        LR.append(input().split())


numbers=[]
for i in range(N+1):
    numbers.append(i)




Lmax=1
Rmax=100000
for j in LR:

    L=int(j[0])
    R=int(j[1])

    if Lmax<L:
        Lmax=L
    if Rmax>R:
        Rmax=R
result=0

for i in numbers:

    if i>=Lmax:

        if i<=Rmax:
            result+=1



print(result)
### BUGGY CODE ###

def find_medians(x, num):
	temp_X = list(x)
	del temp_X[num]
	temp_X.sort()
	return temp_X[int( (len(temp_X)  + 1 ) / 2 - 1)]

N = int(input())
X = list(map(int, input().split()))
for i in range(N):
	print(find_medians(X, i))

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
Y = X.copy()
Y.sort()
for i in range(N):
	if X[i] < Y[int(N / 2)]:
		print(Y[int(N / 2)] )
	else:
		print(Y[int(N / 2 - 1)])
### BUGGY CODE ###

from collections import Counter
N = int(input())
list = [input() for _ in range(0,N)]
counted = Counter(list)
res = [letter for letter,count in counted.most_common() if count == counted.most_common()[0][1]]
[print(i) for i in sorted(res)]

### FIXED CODE ###

from collections import Counter


N = int(input())
list = [input() for _ in range(0,N)]
counted = Counter(list)
res_max= counted.most_common()[0][1]
ans = []
for k, v in counted.items():
    if v == res_max:
        ans.append(k)

ans.sort()
print(*ans, sep="\n")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

k,q=map(int,input().split())
D=tuple(map(int,input().split()))

for query in range(q):
    n,x,m=map(int,input().split())

    D2=[d%m for d in  D]
    S=sum(D2)
    D0=D2.count(0)
    R=(n-1)//k
    ANS=R*(k-D0) - S//m*R-(S%m*R+x%m)//m 

    x2=(x+S%m*R)%m
    rest=n-R*k-1
    S2=sum(D2[:rest])
    DR0=D2[:rest].count(0)
    ANSR=rest - DR0 - (x2+S2)//m

    print(ANS+ANSR)

### FIXED CODE ###

import sys
input = sys.stdin.readline

k,q=map(int,input().split())
D=tuple(map(int,input().split()))

def sum_count(A):
    S=0
    C=0
    for a in A:
        if a==0:
            C+=1
        else:
            S+=a
    return S,C

for query in range(q):
    n,x,m=map(int,input().split())

    D2=[d%m for d in  D]
    S,D0=sum_count(D2)
    R=(n-1)//k
    ANS=R*(k-D0) - (R*S+x%m)//m 
    x2=(x+S*R)%m
    rest=n-R*k-1
    S2,DR0=sum_count(D2[:rest])
    ANSR=rest - DR0 - (x2+S2)//m

    print(ANS+ANSR)
### BUGGY CODE ###

MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))

n_bit = max(a).bit_length()
ans = 0
bit = [0] * n_bit
for i in range(n):
    for j in range(n_bit):
        if (a[i] >> j) & 1:
            ans += (1 << j) * (i - bit[j])
        else:
            ans += (1 << j) * bit[j]
        ans %= MOD

        if (a[i] >> j) & 1:
            bit[j] += 1

print(ans)


### FIXED CODE ###

MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))

n_bit = max(a).bit_length()
b = [(1 << j) % MOD for j in range(n_bit)]

ans = 0
bit = [0] * n_bit
for i in range(n):
    for j in range(n_bit):
        if (a[i] >> j) & 1:
            ans += b[j] * (i - bit[j])
            bit[j] += 1
        else:
            ans += b[j] * bit[j]
        ans %= MOD

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

MOD = 1000000007
def solve(n, m, a):
    dp = [0] * (n+1)
    dp[n] = 1
    for i in range(n-1, -1, -1):
        for d in range(1, 3):
            j = i + d
            if (j <= n) and (not j in a):
                dp[i] = (dp[i] + dp[j]) % MOD
    return dp[0]

n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
print(solve(n, m, a))

### FIXED CODE ###

MOD = 1000000007
def solve(n, m, a):
    a = set(a)
    dp = [0] * (n+1)
    dp[n] = 1
    for i in range(n-1, -1, -1):
        for d in range(1, 3):
            j = i + d
            if (j <= n) and (not j in a):
                dp[i] = (dp[i] + dp[j]) % MOD
    return dp[0]

n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
print(solve(n, m, a))
### BUGGY CODE ###

m = input()
N = list(map(int, input().split(' ')))
# m = int(input())
# k = int(input())
c = 0
for i in N:
    
    if N.count(i) > 1:
        c = 1
        break
if c == 0:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

m = input()
N = list(map(int, input().split(' ')))
# m = int(input())
# k = int(input())
c = 0
N.sort()
for i in range(len(N)-1):
    if N[i] == N[i+1]:
        print('NO')
        exit()

print('YES')
### BUGGY CODE ###

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

    total = 0
    for idx, i in enumerate(A[:-1]):
        for j in range(idx + 1, len(A)):
            total += i * A[j]
    print(total % (10**9 + 7))


def main():
    probC()


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

    sum_tail = sum(A)

    total = 0
    for idx, i in enumerate(A):
        sum_tail -= A[idx]
        if idx + 1 == len(A):
            break
        total += i * sum_tail
    print(total % (10**9 + 7))


def main():
    probC()


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

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

H,W = inpl()

MAP = [list(input()) for y in range(H)]

yokoList = [[0]*W for y in range(H)]

for y in range(H):
    l = 0
    while l < W:
        if MAP[y][l] == '#':
            l += 1
            continue
        else:
            r = l
            tmp = 0
            while True:
                if r >= W or MAP[y][r] == '#':
                    break
                else:
                    r += 1
                    tmp += 1
            for x in range(l,r):
                yokoList[y][x] = tmp
            l = r

tateList = [[0]*W for y in range(H)]

for x in range(W):
    l = 0
    while l < H:
        if MAP[l][x] == '#':
            l += 1
            continue
        else:
            r = l
            tmp = 0
            while True:
                if r >= H or MAP[r][x] == '#':
                    break
                else:
                    r += 1
                    tmp += 1
            for y in range(l,r):
                tateList[y][x] = tmp
            l = r



ans = 0
for y in range(H):
    for x in range(W):
        ans = max(tateList[y][x] + yokoList[y][x]-1, ans)

print(ans)


### FIXED CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

H,W = inpl()

MAP = [list(input()) for y in range(H)]

yokoList = [[0]*W for y in range(H)]

for y in range(H):
    l = 0
    while l < W:
        if MAP[y][l] == '#':
            l += 1
            continue
        else:
            r = l
            tmp = 0
            while True:
                if r >= W or MAP[y][r] == '#':
                    break
                else:
                    r += 1
                    tmp += 1
            for x in range(l,r):
                yokoList[y][x] = tmp
            l = r

tateList = [[0]*W for y in range(H)]

for x in range(W):
    l = 0
    while l < H:
        if MAP[l][x] == '#':
            l += 1
            continue
        else:
            r = l
            tmp = 0
            while True:
                if r >= H or MAP[r][x] == '#':
                    break
                else:
                    r += 1
                    tmp += 1
            for y in range(l,r):
                tateList[y][x] = tmp
            l = r



ans = 0
for y in range(H):
    for x in range(W):
        ans = max(tateList[y][x] + yokoList[y][x]-1, ans)

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

n=int(input())
k=int(input())
count=0
for i in range(1,n+1):
    if len(str(i).replace('0','')) == k:
        count += 1
print(count)

### FIXED CODE ###

N = list(map(int, list(input())))
L = len(N)
K = int(input())
 
dp = [[[0] * (K+1) for j in range(2)] for i in range(L+1)]
dp[0][0][0] = 1
 
for i in range(L):
    ni = N[i]
    if ni == 0:
        for j in range(K):
            dp[i+1][1][j+1] += dp[i][1][j] * 9
        for j in range(K+1):
            dp[i+1][0][j] += dp[i][0][j]
    else:
        for j in range(K+1):
            dp[i+1][1][j] += dp[i][0][j]
        for j in range(K):
            dp[i+1][1][j+1] += (dp[i][0][j] * (ni-1) + dp[i][1][j] * 9)
            dp[i+1][0][j+1] += dp[i][0][j]
 
    for j in range(K+1):
        dp[i+1][1][j] += dp[i][1][j]
 
print(dp[L][0][K]+dp[L][1][K])
### BUGGY CODE ###

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

l=[0]+[float("inf")]*(n-1)

for x in range(n):
    for y in range(x+1,min(n,x+k+1)):
        l[y]=min(l[y],abs(h[y]-h[x])+l[x])

print(l[-1])

### FIXED CODE ###

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

l=[0]+[float("inf")]*(n-1)

for x in range(n):
    for y in range(x+1,min(n,x+k+1)):
        l[y]=min(l[y],abs(h[y]-h[x])+l[x])
print(l[-1])
### BUGGY CODE ###

n=int(input())
s=[str(input()) for _ in range(n)]

from collections import Counter
results = Counter(s)

max_key_list = [kv[0] for kv in results.items() if kv[1] == max(results.values())]
for i in sorted(max_key_list):
  print(i)


### FIXED CODE ###

n=int(input())
s=[str(input()) for _ in range(n)]

from collections import Counter
results = Counter(s)

max_num = results.most_common()[0][1]
max_key_list = [kv[0] for kv in results.items() if kv[1] == max_num]
for i in sorted(max_key_list):
  print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from math import gcd
from functools import reduce
from collections import Counter


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def sieve(n):
    """
    n以下の素数を昇順に列挙する
    """
    is_prime = [True for i in range(n+1)]
    primes = []
    for i in range(2, n+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(i+i, n+1, i):
                is_prime[j] = False
    return primes


def solve(N, A):
    primes = Counter(sieve(10**6))
    for a in A:
        for p in primes:
            if a < p:
                break
            q = a // p
            if q * p == a:
                primes[p] += 1
    if primes.most_common()[0][1] <= 2:
        return "pairwise coprime"
    if reduce(gcd, A) == 1:
        return "setwise coprime"
    return "not coprime"


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


### FIXED CODE ###

import sys
input = sys.stdin.readline
from math import gcd
from functools import reduce
from collections import defaultdict


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def is_pairwise_coprime(A):
    n = max(A)
    base = [False for i in range(n+1)]
    for a in A:
        if a > 1 and base[a]:
            return False
        base[a] = True
    
    is_prime = [True for i in range(n+1)]
    for i in range(2, n+1):
        if is_prime[i]:
            include_number = set()
            if base[i]:
                include_number.add(i)
            for j in range(i+i, n+1, i):
                is_prime[j] = False
                if base[j]:
                    include_number.add(j)
            if len(include_number) >= 2:
                return False
    return True


def solve(N, A):
    if is_pairwise_coprime(A):
        return "pairwise coprime"
    if reduce(gcd, A) == 1:
        return "setwise coprime"
    return "not coprime"


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))
### BUGGY CODE ###

N=int(input())
A=sorted(map(int,input().split()))[::-1]
ans=A[0]
while True:
    M=A[0]
    m=A[1]
    del A[0]
    if M==1:ans=1;break
    if m==0:break
    A.append(M%m)
    A=sorted(A)[::-1]
    ans=min(ans,A[0])
print(ans)

### FIXED CODE ###

import functools,fractions
n=input()
a=list(map(int,input().split()))
print(functools.reduce(fractions.gcd,a))
### BUGGY CODE ###

N,Q=map(int,input().split())
s=input()
A=[]
for i in range (0,N-1):
  if s[i]=="A" and s[i+1]=="C":
    A.append(i+1)
    i += 2
  elif s[i]=="A" and (s[i+1]=="G" or s[i+1]=="T"):
    i += 2
  else:
    i += 1
    
for j in range (0,Q):
  l,r=map(int,input().split())
  print(len([k for k in A if k >= l and k <= r-1]))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
a=[0]*n
k=0
for i in range(n-1):
  if(s[i]=='A' and s[i+1]=='C'):
    k+=1
  a[i]=k
for j in range(q):
  l,r=map(int,input().split())
  if(l==1):
    print(a[r-2])
  else:
    print(a[r-2]-a[l-2])
### BUGGY CODE ###

s = input()
ans = 0
for i in range(4,len(s)):
    for j in range(len(s)+1-i):
        t=s[j:j+i]
        if int(t)%2019==0:
            ans+=1
print(ans)

### FIXED CODE ###

from collections import Counter

n = list(input())
n.reverse()
x = [0]*(len(n))
a=0
ex=1
for i in range(len(n)):
    a+=int(n[i])*ex
    x[i]=a%2019
    ex=ex*10%2019
c=Counter(x)
ans = c[0]
for i in c.keys():
    b=c[i]
    ans += b*(b-1)//2

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

N, Q = list(map(int, input().split()))
S = input()

a = [0] * len(S)

for i in range(len(S)):
    if S[i:i+2] == "AC":
        a[i] = 1

for q in range(Q):
    l, r = list(map(int, input().split()))
    print(sum(a[l-1: r-1]))


### FIXED CODE ###

N, Q = list(map(int, input().split()))
S = input()

a = [0] * N

count = 0
for i in range(1, N):
    if S[i-1:i+1] == "AC":
        count += 1
    a[i] = count


for q in range(Q):
    l, r = list(map(int, input().split()))
    print(a[r-1] - a[l-1])
### BUGGY CODE ###

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

rc = 0
gc = 0
bc = 0

for si in S:
    if si == 'R':
        rc += 1
    elif si == 'G':
        gc += 1
    else:
        bc += 1


bad = 0
for i in range(N):
    for j in range(i+1, N):
        k = j + (j-i)
        if k > N-1:
            continue
        
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            # print('bad', i,j,k,S[i],S[j],S[k])
            bad += 1

ans = rc * gc * bc
# print(ans)
ans -= bad
print(ans)


### FIXED CODE ###

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

rc = 0
gc = 0
bc = 0

for si in S:
    if si == 'R':
        rc += 1
    elif si == 'G':
        gc += 1
    else:
        bc += 1


bad = 0
for i in range(N):
    for j in range(i+1, N):
        k = j + (j-i)
        if k > N-1:
            continue
        
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            # print('bad', i,j,k,S[i],S[j],S[k])
            bad += 1

ans = rc * gc * bc
# print(ans)
ans -= bad
print(ans)
### BUGGY CODE ###

import numpy as np
n=int(input())
a = list(input().split())
a = [int(i) for i in a]
q=int(input())
bc=[list(map(int,input().split())) for i in range(q)]
bc=np.array(bc).T
b=bc[0]
c=bc[1]

ans=sum(a)
for i in range(q):
  #print(a)
  count=a.count(b[i])
  ans+=(c[i]-b[i])*count
  print(ans)
  a=[c[i] if b[i]==a[ii] else a[ii] for ii in range(n)]
  
  

### FIXED CODE ###

import numpy as np
from collections import Counter as C

n=int(input())
a = list(input().split())
a = [int(i) for i in a]
q=int(input())
bc=[list(map(int,input().split())) for i in range(q)]
bc=np.array(bc).T
b=bc[0]
c=bc[1]

d=C(a)
d2={}
for k,v in d.items():
  d2[k]=k*v

#print(d)
ans=sum(a)
for i in range(q):
  d[c[i]]+=d[b[i]]
  ans+=(c[i]-b[i])*d[b[i]]
  d[b[i]]=0
  print(ans)
### BUGGY CODE ###

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

attendance = []

for i in range(1, N+1):
    attendance.append(l.index(i)+1)

print(*attendance)


### FIXED CODE ###

N = int(input())
A = map(int, input().split())
L = [0] * N

for i,val in enumerate(A):
    L[val-1] = i + 1

print(*L)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 1000000007
ans = 0
for n in range(1,N):
    for k in range(n,N):
        ans += A[n-1] * A[k]
print(ans % MOD)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 1000000007
SUM = sum(A) % MOD
ans = 0

for n in A:
    SUM -= n
    SUM %= MOD
    ans += SUM * n
    ans %= MOD

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

# 0 ≦ X, Y, Z ≦ K
# X + Y + Z = S
# 2 ≦ K ≦ 2500
# 0 ≦ S ≦ 3K

K, S = list(map(int, input().split()))

cnt = 0
# X
for i in range(K + 1):
    # Y
    for j in range(K + 1):
        # Z
        for k in range(K + 1):
            if i + j + k > S:
                break
            if i + j + k == S:
                cnt += 1
print(cnt)


### FIXED CODE ###

# 0 ≦ X, Y, Z ≦ K
# X + Y + Z = S
# 2 ≦ K ≦ 2500
# 0 ≦ S ≦ 3K

K, S = list(map(int, input().split()))

cnt = 0
# X
for i in range(K + 1):
    # Y
    for j in range(K + 1):
        Z = S - i - j
        if 0 <= Z and Z <= K:
            cnt += 1
print(cnt)
### BUGGY CODE ###

X,Y=map(int,input().split())
if X==Y:
  print(-1)
  exit()
  
i = 2
while True:
  if X*i % Y != 0 and X*i <= 10**18:
    print(X*i)
    exit()
  i += 1
  if X*i > 10**18:
    print(-1)
    exit()

### FIXED CODE ###

X,Y=map(int,input().split())
if X%Y==0:
  print(-1)
  exit()
  
i = 2
while True:
  if X*i % Y != 0 and X*i <= 10**18:
    print(X*i)
    exit()
  i += 1
  if X*i > 10**18:
    print(-1)
    exit()
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
count = 0  
k = int(input())
for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      count+=gcd(a, b, c)
print(count)

### FIXED CODE ###

import math
count = 0  
k = int(input())
for a in range(1,k+1):
  for b in range(a,k+1):
    for c in range(b,k+1):
      d = math.gcd(a,b)
      e = math.gcd(d,c)
      if a==b==c:
        count+=e
      elif a==b or b==c or c==a:
        count+=e*3
      else:
        count+=e*6
print(count)
### BUGGY CODE ###

#!/usr/bin/env python3
#EDPC P

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
graph = [[] for _ in range(n)]
for _ in range(n-1):
    x,y = LI()
    graph[x-1].append(y-1)
    graph[y-1].append(x-1)

dp = [[1,1] for _ in range(n)]
flg = [0]*n
def f(v):
    flg[v] = 1
    for u in graph[v]:
        if flg[u]:
            continue
        f(u)
        dp[v][0] = dp[v][0]*(dp[u][0]+dp[u][1])
        dp[v][0] %= mod
        dp[v][1] = dp[v][1]*dp[u][0]
        dp[v][1] %= mod

f(0)
ans = (dp[0][0] + dp[0][1]) % mod
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
#EDPC P

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
graph = [[] for _ in range(n)]
for _ in range(n-1):
    x,y = LI()
    graph[x-1].append(y-1)
    graph[y-1].append(x-1)

dp = [[1,1] for _ in range(n)]
flg = [0]*n
def f(v):
    flg[v] = 1
    for u in graph[v]:
        if flg[u]:
            continue
        f(u)
        dp[v][0] *= (dp[u][0]+dp[u][1])
        dp[v][0] %= mod
        dp[v][1] *= dp[u][0]
        dp[v][1] %= mod

f(0)
ans = (dp[0][0] + dp[0][1]) % mod
print(ans)