Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

ans = 0
x = 1

while 1:
    if n % x == 0:
        m = n // x - 1
        if m <= x:
            break
        else:
            ans += m
    x += 1

print(ans)

Fixed submission:
n = int(input())

if n < 100000:

    ans = 0
    x = 1

    while x < n:
        if n % x == 0:
            m = n // x - 1
            if m <= x:
                break
            else:
                ans += m
        x += 1

    print(ans)

    exit()


ans = 0
x = 1

t = int(n ** 0.5)

while x <= int(n ** 0.5):
    if n % x == 0:
        ans += n // x - 1
    x += 1

if t * t == n:
    ans -= t - 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

ans = 0
x = 1

while x < n:
    if n % x == 0:
        m = n // x - 1
        if m <= x:
            break
        else:
            ans += m
    x += 1

print(ans)

Fixed submission:
n = int(input())

if n < 100000:

    ans = 0
    x = 1

    while x < n:
        if n % x == 0:
            m = n // x - 1
            if m <= x:
                break
            else:
                ans += m
        x += 1

    print(ans)

    exit()


ans = 0
x = 1

t = int(n ** 0.5)

while x <= int(n ** 0.5):
    if n % x == 0:
        ans += n // x - 1
    x += 1

if t * t == n:
    ans -= t - 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

ans = 0
x = 1

while x < n:
    if n % x == 0:
        m = n // x - 1
        if m <= x:
            break
        else:
            ans += m
    x += 1

print(ans)

Fixed submission:
n = int(input())

if n < 100000:

    ans = 0
    x = 1

    while x < n:
        if n % x == 0:
            m = n // x - 1
            if m <= x:
                break
            else:
                ans += m
        x += 1

    print(ans)

    exit()


ans = 0
x = 1

t = int(n ** 0.5)

while x <= int(n ** 0.5):
    if n % x == 0:
        ans += n // x - 1
    x += 1

if t * t == n:
    ans -= t - 1

print(ans)
Buggy python submission (verdict: Runtime Error):
h, w = map(int, input().split())
a = [['*' for _ in range(w+2)]]
for _ in range(h):
    a.append(['*'] + list(input()) + ['*'])
a.append(['*' for _ in range(w+2)])

q = set()

def encode(i, j):
    return i*w + j

def decode(x):
    i = x // w
    j = x % w
    return [i, j]

for i in range(1, h+1):
    for j in range(1, w+1):
        if a[i][j] == '#':
            q.add(encode(i, j))

for ans in range(h+w):
    nq = set()
    for x in q:
        i, j = decode(x)
        for k in [-1,1]:
            if a[i+k][j] == '.':
                nq.add(encode(i+k, j))
                a[i+k][j] = '#'
        for k in [-1,1]:
            if a[i][j+k] == '.':
                nq.add(encode(i, j+k))
                a[i][j+k] = '#'
    if len(nq) == 0:
        print(ans)
        exit()
    else:
        q = set()
        q = q | nq


Fixed submission:
h, w = map(int, input().split())
a = [['*' for _ in range(w+2)]]
for _ in range(h):
    a.append(['*'] + list(input()) + ['*'])
a.append(['*' for _ in range(w+2)])

q = set()

def encode(i, j):
    return i*w + j-1

def decode(x):
    i = x // w
    j = x % w + 1
    return [i, j]

for i in range(1, h+1):
    for j in range(1, w+1):
        if a[i][j] == '#':
            q.add(encode(i, j))

for ans in range(h+w):
    nq = set()
    for x in q:
        i, j = decode(x)
        for k in [-1,1]:
            if a[i+k][j] == '.':
                nq.add(encode(i+k, j))
                a[i+k][j] = '#'
        for k in [-1,1]:
            if a[i][j+k] == '.':
                nq.add(encode(i, j+k))
                a[i][j+k] = '#'
    if len(nq) == 0:
        print(ans)
        exit()
    else:
        q = set()
        q = q | nq
Buggy python submission (verdict: Runtime Error):
from collections import Counter

n, q = map(int, input().split())
s = list(input())
td = [list(input().split()) for _ in range(q)]

if n == 1:
    for t, d in td:
        if s[0] == t:
            print(0)
            exit()
    print(1)
    exit()

def vanish(x):
    for t, d in td:
        if s[x] == t:
            if d == 'L':
                x -= 1
                if x == -1:
                    return -1
            else:
                x += 1
                if x == n:
                    return n
    return x

L = 0
R = n
U = 0
ans = n

while R - L > 1:
    M = (L + R) // 2
    ret = vanish(M)
    if ret == -1:
        L = M
    elif ret == n:
        R = M
        U = M
    else:
        R = M

ret = vanish(L)
if ret == -1:
    ans -= L + 1
    U = max(U, L + 1)
else:
    ans -= L

L = U
R = n

while R - L > 1:
    M = (L + R) // 2
    ret = vanish(M)
    if ret == n:
        R = M
    else:
        L = M

ret = vanish(L)
if ret == n:
    ans -= n - L
else:
    ans -= n - 1 - L

print(ans)




Fixed submission:
from collections import Counter

n, q = map(int, input().split())
s = list(input())
td = [list(input().split()) for _ in range(q)]

if n == 1:
    for t, d in td:
        if s[0] == t:
            print(0)
            exit()
    print(1)
    exit()

def vanish(x):
    for t, d in td:
        if s[x] == t:
            if d == 'L':
                x -= 1
                if x == -1:
                    return -1
            else:
                x += 1
                if x == n:
                    return n
    return x

L = 0
R = n
U = 0
ans = n

while R - L > 1:
    M = (L + R) // 2
    ret = vanish(M)
    if ret == -1:
        L = M
    else:
        R = M

ret = vanish(L)
if ret == -1:
    ans -= L + 1
else:
    ans -= L

L = 0
R = n

while R - L > 1:
    M = (L + R) // 2
    ret = vanish(M)
    if ret == n:
        R = M
    else:
        L = M

ret = vanish(L)
if ret == n:
    ans -= n - L
else:
    ans -= n - 1 - L

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, x = map(int, input().split())
a = list(map(int, input().split()))

a.sort()

MOD = 10 ** 9 + 7

S = [0] * (x+1)
T = [0] * (x+1)

S[x] = 1

for i in range(n-1, -1, -1):
    T = [0] * (x + 1)
    for j in range(x+1):
        S[j] %= MOD
        T[j] += S[j] * i % MOD
        T[j % a[i]] += S[j]
    S, T = T, S

print(sum(i * S[i] % MOD for i in range(a[0]) ) % MOD)


Fixed submission:
n, x = map(int, input().split())
a = list(map(int, input().split()))

a.sort()

MOD = 10 ** 9 + 7

S = [0] * (x+1)
T = [0] * (x+1)

S[x] = 1

for i in range(n-1, -1, -1):
    T = [0] * (x + 1)
    for j in range(x+1):
        S[j] %= MOD
        T[j] += S[j] * i % MOD
        T[j % a[i]] += S[j]
    S, T = T, S

print(sum(i * S[i] % MOD for i in range(a[0]) ) % MOD)
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
ab = [tuple(int(x) for x in input().split()) for _ in range(m)]

ans = [n * (n - 1) // 2 for _ in range(m + 1)]

u = [-1 for _ in range(n)]

def root(x):
    if u[x] < 0:
        return x
    else:
        u[x] = root(u[x])
        return u[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    if size(x) < size(y):
        x, y = y, x
    u[x] += u[y]
    u[y] = x

def size(x):
    return - u[root(x)]

i = m - 1
for a, b in list(reversed(ab)):
    if root(a - 1) == root(b - 1):
        ans[i] = ans[i + 1]
    else:
        ans[i] = ans[i + 1] - size(a - 1) * size(b - 1)
        unite(a - 1, b - 1)
    i -= 1

for i in range(1, m + 1):
    print(ans[i])

Fixed submission:
n, m = map(int, input().split())
ab = [tuple(int(x) for x in input().split()) for _ in range(m)]

class UnionFind:
    def __init__(self, size):
        self.rank = [-1 for _ in range(size)]
        self.number = [1 for _ in range(size)]

    def find(self, x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x

    def union(self, s1, s2):
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]

uft = UnionFind(n)
ans = [0 for _ in range(m)]
temp = n * (n - 1) // 2
ans[m - 1] = temp
for i in range(m-1, 0, -1):
    ra = uft.find(ab[i][0] - 1)
    rb = uft.find(ab[i][1] - 1)
    if ra != rb:
        temp -= uft.number[ra] * uft.number[rb]
        uft.union(ra, rb)
    ans[i - 1] = temp

for x in ans:
    print(x)
Buggy python submission (verdict: Runtime Error):
n = int(input())
x = list(map(int, input().split))

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

while len(x) > 1:
    i = 0
    next = []
    while i < len(x) - 1:
        next.append(gcd(x[i], x[i+1]))
        i += 2

    x = [] + next

print(x[0])

Fixed submission:
n = int(input())
x = list(map(int, input().split()))

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

while len(x) > 1:
    i = 0
    next = []
    while i < len(x) - 1:
        next.append(gcd(x[i], x[i+1]))
        i += 2

    x = [] + next

print(x[0])

Buggy python submission (verdict: Runtime Error):
import numpy as np

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

def numpy_gcd(a, b):
    a, b = np.broadcast_arrays(a, b)
    a = a.copy()
    b = b.copy()
    pos = np.nonzero(b)[0]
    while len(pos) > 0:
        b2 = b[pos]
        a[pos], b[pos] = b2, a[pos] % b2
        pos = pos[b[pos] != 0]
    return a

while len(x) > 1:
    i = 0
    next = []
    while i < len(x) - 1:
        next.append(numpy_gcd(x[i],x[i+1]))
        i += 2

    x = [] + next

print(x[0])

Fixed submission:
n = int(input())
x = list(map(int, input().split()))

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

while len(x) > 1:
    i = 0
    next = []
    while i < len(x) - 1:
        next.append(gcd(x[i], x[i+1]))
        i += 2

    x = [] + next

print(x[0])
Buggy python submission (verdict: Time Limit Exceeded):
from operator import itemgetter

n, m = map(int, input().split())
a = list(map(int, input().split()))

b = [2, 5, 5, 4, 5, 6, 3, 7, 6]

c = []

for x in a:
    if x in [1, 4, 7, 8]:
        c.append((str(x), b[x - 1]))

if 5 in a:
    c.append(('5', 5))
elif 3 in a:
    c.append(('3', 5))
elif 2 in a:
    c.append(('2', 5))

if 9 in a:
    c.append(('9', 6))
elif 6 in a:
    c.append(('6', 6))

c = sorted(c, key=itemgetter(1), reverse=True)

dp = [0 for _ in range(n + 8)]

for x, y in c:
    dp[y] = int(x)

for i in range(2, n + 1):
    if dp[i] == 0:
        continue
    for x, y in c:
        dp[i + y] = max(dp[i + y], int(x + str(dp[i])))

print(dp[n])




Fixed submission:
from operator import itemgetter

n, m = map(int, input().split())
a = list(map(int, input().split()))

b = [2, 5, 5, 4, 5, 6, 3, 7, 6]

c = []

for x in a:
    if x in [1, 4, 7, 8]:
        c.append((x, b[x - 1]))

if 5 in a:
    c.append((5, 5))
elif 3 in a:
    c.append((3, 5))
elif 2 in a:
    c.append((2, 5))

if 9 in a:
    c.append((9, 6))
elif 6 in a:
    c.append((6, 6))

c = sorted(c, key=itemgetter(1), reverse=True)

dp = [-999999 for _ in range(n + 1)]
dp[0] = 0

for i in range(2, n + 1):
    for x, y in c:
        if i >= y:
            dp[i] = max(dp[i], dp[i - y] + 1)
    #print(i, dp)

c = sorted(c, key=itemgetter(0), reverse=True)

#print(c)
#print(dp)

s = []
k = dp[n]
while k > 0:
    #print(s, k)
    #input()
    for x, y in c:
        if n >= y:
            if dp[n - y] == k - 1:
                s.append(str(x))
                k -= 1
                n -= y
                break

print(int(''.join(s)))
Buggy python submission (verdict: Runtime Error):
from operator import itemgetter

n, k = map(int, input().split())
td = [tuple(int(x) for x in input().split()) for _ in range(n)]

a = sorted(td, key=itemgetter(1), reverse=True)

ans = [0]
s = set()
t = []
for i in range(k):
    ans[0] += a[i][1]
    if a[i][0] not in s:
        s.add(a[i][0])
    else:
        t.append(a[i][1])

p = len(s)
q = len(t) - 1

if q < 0:
    print(ans[0] + k * k)
    exit()

v = []
for i in range(k, n):
    if a[i][0] not in s:
        s.add(a[i][0])
        v.append(a[i][1])

ans[0] += p * p
d = 0

for x in v:
    ans.append(ans[d] + x - t[q] + (p + 1) * (p + 1) - p * p)
    p += 1
    d += 1
    q -= 1
    if q < 0:
        break

print(max(ans))

Fixed submission:
a = list(map(int, input().split()))

a = sorted(a)

print(a[0] * a[1] // 2)
Buggy python submission (verdict: Time Limit Exceeded):
s = list(input())
t = list(input())

n = len(s)
m = len(t)

dp = [[0 for _ in range(m+1)] for _ in range(n+1)]

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])

ans = ''
i = n
j = m
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] + ans;
        i -= 1
        j -= 1

print(ans)

Fixed submission:
s = list(input())
t = list(input())

n = len(s)
m = len(t)

dp = [[0 for _ in range(m+1)] for _ in range(n+1)]

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])

ans = ''
i = n
j = m
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] + ans;
        i -= 1
        j -= 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
p = list(map(float, input().split()))

dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    dp[i+1][0] = dp[i][0] * (1-p[i])
    for j in range(1, i+2):
        dp[i+1][j] = dp[i][j] * (1-p[i]) + dp[i][j-1] * p[i]

print(sum(dp[n][n // 2 + 1:]))


Fixed submission:
n = int(input())
p = list(map(float, input().split()))

dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    dp[i+1][0] = dp[i][0] * (1-p[i])
    for j in range(1, i+2):
        dp[i+1][j] = dp[i][j] * (1-p[i]) + dp[i][j-1] * p[i]

print(sum(dp[n][n // 2 + 1:]))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

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

c = Counter(a)

dp = [[[0.0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]

for z in range(c[3] + 1):
    for y in range(c[2]+1 + c[3] - z):
        for x in range(n+1 - z - y):
            if x + y + z == 0:
                continue
            ret = 0.0
            if x > 0:
                ret += dp[x-1][y][z] * x
            if y > 0:
                ret += dp[x+1][y-1][z] * y
            if z > 0:
                ret += dp[x][y+1][z-1] * z
            dp[x][y][z] = (ret + n) / (x + y + z)

print(dp[c[1]][c[2]][c[3]])


Fixed submission:
from collections import Counter

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

c = Counter(a)

dp = [[[0.0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]

for z in range(c[3] + 1):
    for y in range(c[2]+1 + c[3] - z):
        for x in range(n+1 - z - y):
            if x + y + z == 0:
                continue
            ret = 0.0
            if x > 0:
                ret += dp[x-1][y][z] * x
            if y > 0:
                ret += dp[x+1][y-1][z] * y
            if z > 0:
                ret += dp[x][y+1][z-1] * z
            dp[x][y][z] = (ret + n) / (x + y + z)

print(dp[c[1]][c[2]][c[3]])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

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

c = Counter(a)

dp = [[[-1 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]

def sushi(x, y, z):
    if dp[x][y][z] >= 0:
        return dp[x][y][z]
    if x == 0 and y == 0 and z == 0:
        return 0.0

    ret = 0.0
    if x > 0:
        ret += sushi(x-1, y, z) * x
    if y > 0:
        ret += sushi(x+1, y-1, z) * y
    if z > 0:
        ret += sushi(x, y+1, z-1) * z
    dp[x][y][z] = (ret + n) / (x + y + z)
    return dp[x][y][z]

print(sushi(c[1], c[2], c[3]))


Fixed submission:
from collections import Counter

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

c = Counter(a)

dp = [[[0.0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]

for z in range(c[3] + 1):
    for y in range(c[2]+1 + c[3] - z):
        for x in range(n+1 - z - y):
            if x + y + z == 0:
                continue
            ret = 0.0
            if x > 0:
                ret += dp[x-1][y][z] * x
            if y > 0:
                ret += dp[x+1][y-1][z] * y
            if z > 0:
                ret += dp[x][y+1][z-1] * z
            dp[x][y][z] = (ret + n) / (x + y + z)

print(dp[c[1]][c[2]][c[3]])
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = list(map(int, input().split()))

t = min(a)

dp = [0] * (k+1)

for x in a:
    dp[x] = 1

for i in range(k+1):
    for x in a:
        if i >= x:
            if dp[i] + (dp[i-x] + 1) % 2 > 0:
                dp[i] = 1
            else:
                dp[i] = 0

print("First" if dp[i] == 1 else "Second")

Fixed submission:
n, k = map(int, input().split())
a = list(map(int, input().split()))

t = min(a)

dp = [0] * (k+1)

for x in a:
    dp[x] = 1

for i in range(k+1):
    for x in a:
        if i >= x:
            if dp[i] + (dp[i-x] + 1) % 2 > 0:
                dp[i] = 1
            else:
                dp[i] = 0

print("First" if dp[i] == 1 else "Second")

Buggy python submission (verdict: Runtime Error):
from collections import Counter

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

c = Counter(a)

dp = [[[0.0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]

for z in range(c[3] + 1):
    for y in range(c[2]+1 + c[3] - z):
        for x in range(n+1 - z - y):
            if x + y + z == 0:
                continue
            ret = 0.0
            if x > 0:
                ret += dp[x-1][y][z] * x
            if y > 0:
                ret += dp[x+1][y-1][z] * y
            if z > 0:
                ret += dp[x][y+1][z-1] * z
            dp[x][y][z] = (ret + n) / (x + y + z)

print(dp[c[1]][c[2]][c[3]])


Fixed submission:
n, k = map(int, input().split())
a = list(map(int, input().split()))

t = min(a)

dp = [0] * (k+1)

for x in a:
    dp[x] = 1

for i in range(k+1):
    for x in a:
        if i >= x:
            if dp[i] + (dp[i-x] + 1) % 2 > 0:
                dp[i] = 1
            else:
                dp[i] = 0

print("First" if dp[i] == 1 else "Second")
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

INF = 10 ** 20

dp = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
    dp[i][i] = 0

for k in range(1, n):
    for x in range(n-k):
        y = x + k
        temp = INF
        for i in range(k):
            temp = min(temp, dp[x][x+i] + dp[x+i+1][y] + sum(a[x:y+1]))
        dp[x][y] = temp

print(dp[0][n-1])

Fixed submission:
n = int(input())
a = list(map(int, input().split()))

INF = 10 ** 20

dp = [[0 for _ in range(n)] for _ in range(n)]

s = [0] * (n+1)
for i in range(n):
    s[i+1] = s[i] + a[i]


for i in range(n):
    dp[i][i] = 0

for k in range(1, n):
    for x in range(n-k):
        y = x + k
        temp = INF
        for i in range(k):
            temp = min(temp, dp[x][x+i] + dp[x+i+1][y] + s[y+1] - s[x])
        dp[x][y] = temp

print(dp[0][n-1])

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

INF = 10 ** 20

dp = [[INF for _ in range(n)] for _ in range(n)]

for i in range(n):
    dp[i][i] = 0

for k in range(1, n):
    for x in range(n-k):
        y = x + k
        for i in range(k):
            dp[x][y] = min(dp[x][y], dp[x][x+i] + dp[x+i+1][y] + sum(a[x:y+1]))

print(dp[0][n-1])

Fixed submission:
n = int(input())
a = list(map(int, input().split()))

INF = 10 ** 20

dp = [[0 for _ in range(n)] for _ in range(n)]

s = [0] * (n+1)
for i in range(n):
    s[i+1] = s[i] + a[i]


for i in range(n):
    dp[i][i] = 0

for k in range(1, n):
    for x in range(n-k):
        y = x + k
        temp = INF
        for i in range(k):
            temp = min(temp, dp[x][x+i] + dp[x+i+1][y] + s[y+1] - s[x])
        dp[x][y] = temp

print(dp[0][n-1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(1000000)

MOD = 10 ** 9 + 7

n = int(input())

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

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

def treeDP(p):
    if len(ab[p]) == 0:
        return [2,1]
    else:
        f = 1
        g = 1
        for x in ab[p]:
            ab[x].remove(p)
            temp = treeDP(x)
            f *= temp[1]
            g *= temp[0]
        f += g
        return [f % MOD, g % MOD]

print(treeDP(0)[0])


Fixed submission:
import sys

sys.setrecursionlimit(1000000)

MOD = 10 ** 9 + 7

n = int(input())

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

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

def treeDP(p):
    if len(ab[p]) == 0:
        return [2,1]
    else:
        f = 1
        g = 1
        for x in ab[p]:
            ab[x].remove(p)
            temp = treeDP(x)
            f *= temp[1]
            g *= temp[0]
        f += g
        return [f % MOD, g % MOD]

print(treeDP(0)[0])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

a.sort(reverse=True)

ans = 0
while len(a) > 1:
    x = a[0]
    del a[0]
    temp = (1 << x.bit_length()) - x
    if temp in a:
        ans += 1
        a.remove(temp)

print(ans)



Fixed submission:
from collections import Counter

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

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

ans = 0
for x in a:
    if c[x] == 0:
        continue
    temp = (1 << x.bit_length()) - x
    c[x] -= 1
    if temp in c.keys():
        if c[temp] > 0:
            c[temp] -= 1
            ans += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left

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

a = sorted(a)

temp = 2
while temp <= a[len(a) - 1]:
    temp *= 2

ans = 0
while len(a) > 1:
    m = a[len(a) - 1]
    del a[len(a) - 1]
    while 1:
        if temp > m * 2:
            temp //= 2
        else:
            break
    if temp < m:
        temp *= 2
        continue
    if (temp - m) in a:
        ans += 1
        a.remove(temp - m)

print(ans)



Fixed submission:
from collections import Counter

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

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

ans = 0
for x in a:
    if c[x] == 0:
        continue
    temp = (1 << x.bit_length()) - x
    c[x] -= 1
    if temp in c.keys():
        if c[temp] > 0:
            c[temp] -= 1
            ans += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

a = sorted(a)
ans = 0
while len(a) > 1:
    m = a[len(a) - 1]
    del a[len(a) - 1]
    temp = 2
    for i in range(n):
        if temp > m:
            break
        else:
            temp *= 2
    if temp > m * 2:
        continue
    if (temp - m) in a:
        ans += 1
        a.remove(temp - m)

print(ans)



Fixed submission:
from collections import Counter

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

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

ans = 0
for x in a:
    if c[x] == 0:
        continue
    temp = (1 << x.bit_length()) - x
    c[x] -= 1
    if temp in c.keys():
        if c[temp] > 0:
            c[temp] -= 1
            ans += 1

print(ans)