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

N=int(input())
vertexes=[[] for i in range(N)]
edges=[[int(s) for s in input().split()] for i in range(N-1)]
#頂点ごとに、頂点から伸びる辺のデータを記録
for e in edges:
  vertexes[e[0]-1].append([e[1]-1,e[2]])
  vertexes[e[1]-1].append([e[0]-1,e[2]])

#幅優先探索の開始（v_possibleに入った順に頂点を訪れる）
answer=[-1 for i in range(N)]  #到達していない頂点は-1
answer[0]=0
v_possible=[] #到達可能な頂点と、辺の情報
v=0 #現在の位置
for i in range(N-1):
  for e in vertexes[v]: #行き先の更新
    v_possible.append([e[0],v,e[1]]) #[行き先,つながる頂点,距離]
  Len=len(v_possible)
  x=0
  for k in range(Len):
    vx=v_possible[k-x]
    if answer[vx[0]]==-1: #まだ訪れていないなら移動
      answer[vx[0]]=(answer[vx[1]]+vx[2])%2
      v=vx[0]
      break
    else: #すでに訪れたなら、その情報は消す
      del v_possible[k-x]
      x+=1

#答を出力
for i in range(N):
  print(answer[i])


### FIXED CODE ###

N = int(input())
edge = [set() for i in range(N)]
for i in range(N-1): #辺の情報と距離を記録
  u, v, w = map(int, input().split())
  edge[u-1].add((v-1, w))
  edge[v-1].add((u-1, w))

#幅優先検索
dist = [0] * N #距離
stack = [0]
while stack: #stackが空になるまで
  vrt = stack.pop()
  for to, w in edge[vrt].copy():
    stack.append(to)
    dist[to] = dist[vrt] + w
    edge[vrt].discard((to, w))
    edge[to].discard((vrt, w))
    
for i in range(N):
  print(dist[i]%2)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
cnt = [0]*5
for i in range(n):
    cnt[a[i]] += 1
maxn = 301
memo = [[[-1]*maxn for i in range(maxn)]for j in range(maxn)]
def dp(i,j,k):
    if i==0 and j==0 and k==0:
        return 0.0
    
    if memo[i][j][k] != -1:
        return memo[i][j][k]

    res = 0
    if i>0:
        res += i*dp(i-1,j+1,k)
    if j>0:
        res += j*dp(i,j-1,k+1)
    if k>0:
        res += k*dp(i,j,k-1)
    res += n
    res /= (i+j+k)
    memo[i][j][k]=res
    return res

print(dp(cnt[3],cnt[2],cnt[1]))

### FIXED CODE ###

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

dp = [[[0 for _ in range(301)]for __ in range(301)]for ___ in range(301)]

for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            cnt = i + j + k
            if cnt == 0 or cnt > n :continue
            if i == 0 and j ==0 and k ==1:
                dp[i][j][k] = 1
                continue
            if k > 0:
                dp[i][j][k] += (1+dp[i][j][k-1] * cnt/(cnt-1))*k/cnt
            if j > 0:
                dp[i][j][k] += (1+dp[i][j-1][k+1])*j/cnt
            if i > 0:
                dp[i][j][k] += (1+dp[i-1][j+1][k])*i/cnt 
            
print(dp[a.count(3)][a.count(2)][a.count(1)])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
from itertools import chain
import numpy as np
h,w=map(int,input().split())
s=[list(input())for i in range(h)]
a=[[float("inf")]*w for i in range(h)]
b=[[False]*w for i in range(h)]
d=set()
def f(x,y,t):
    if 0<=x<h and 0<=y<w:
        if s[x][y]=="#":
            if b[x][y]==False:
                a[x][y]=0
                b[x][y]=True
                f(x,y+1,1)
                f(x+1,y,1)
                f(x-1,y,1)
                f(x,y-1,1)
        else:
            if a[x][y]>t:
                a[x][y]=t
                f(x,y+1,t+1)
                f(x+1,y,t+1)
                f(x-1,y,t+1)
                f(x,y-1,t+1)
i,j=divmod(list(chain(*s)).index("#"), len(s[0]))
f(i,j,0)
print(max(max(i)for i in a))

### FIXED CODE ###

import numpy as np
from scipy.ndimage import distance_transform_cdt as d
h,w=map(int,input().split())
s=[[1 if i=="." else 0 for i in input()]for i in range(h)]
a=d(s,metric='taxicab')
print(a.max())
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError("n is int-type.")
    if n < 2:
        raise ValueError("n is more than 2")
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data

n = inp()
if n == 1:
    print(1)
    quit()
cnt = 1
res = 1
ans = [-1] * (n+1)
ans[1] = 1 
pl = get_sieve_of_eratosthenes(n)
for x in pl:
    # print(x)
    cnt += 1
    ans[x] = 2
    res += 2*x
    c = 2
    while pow(x,c) <= n:
        now = pow(x,c)
        if ans[now] == -1:
            ans[now] = c+1
            res += now*(c+1)
            cnt += 1
        c += 1
# print(ans)
while cnt < n:
    for i in range(2,n+1):
        for j in range(i+1,n+1):
            if i * j > n: break
            if math.gcd(i,j) != 1 or ans[i*j] != -1: continue
            if ans[j] == -1: continue
            ans[i*j] = ans[i] * ans[j]
            res += (i*j) * ans[i*j]
            cnt += 1
# print(ans)
# for i in range(1,n+1):
#     res += ans[i] * i
#     if ans[i] < -1:
#         print(i)
print(res)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
ans = [0] * (n+1)
for i in range(1,n+1):
    for j in range(1,n+1):
        if i*j > n: break
        ans[i*j] += 1
res = 0
for i in range(1,n+1):
    res += i*ans[i]
print(res)
### BUGGY CODE ###

a, b = map(int, input().split())
g = []
def gcd(x,y):
   while(y):
       x,y=y,x%y
   return x
g.append(gcd(a,b))
g.append(1)
if not a%2 and not b%2:
    g.append(2)
for i in range(3,g[0],2):
    if not a%i and not b%i:
        c = True
        for k in range(2, len(g)):
            if gcd(g[k],i)!=1:
                c = False
                break
        if c:
            g.append(i)
c = True
for i in range(1, len(g)):
    if gcd(g[0],g[i])!=1:
        c = False
        break
if c and g[0] != 1:
    print(len(g))
else:
    print(len(g)-1)

### FIXED CODE ###

a, b = map(int, input().split())
def factor(n):
    a = []
    while not n%2:
       n//=2
       a.append(2)
    i = 3
    while i*i<=n:
        while not n%i:
            n//=i
            a.append(i)
        i+=2
    if n>1:
        a.append(n)
    return a
print(len(set(factor(a))&set(factor(b)))+1)
### BUGGY CODE ###

N, M = map(int, input().split())
A_list = list(map(int, input().split()))
A_list.sort()
for j in range(M):
    B, C = map(int, input().split())
    for k in range(B):
        if A_list[k] < C:
            A_list[k] = C
        else:
            break
    A_list.sort()
print(sum(A_list))

### FIXED CODE ###

N, M = map(int, input().split())
A_list = list(map(int, input().split()))
A_list.sort()

BC_list = [list(map(int, input().split())) for _ in range(M)]
BC_list = sorted(BC_list, key=lambda x: x[1])

ans = 0
count = 0
i = N-1
m = M-1
while count < N:
    if A_list[i] < BC_list[m][1]:
        for _ in range(BC_list[m][0]):
            ans += BC_list[m][1]
            count += 1
            if count >= N:
                break
        m -= 1
    else:
        ans += A_list[i]
        count += 1
        i -= 1

    if m < 0:
        break

for _ in range(count, N):
    ans += A_list[i]
    i -= 1

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

input()
l = map(int, input().split())
r = 1
for i in l:
    r *= i
print(-1 if r > 1e18 else r)

### FIXED CODE ###

input()
l = list(map(int, input().split()))
if 0 in l:
    print(0)
else:
    r = 1
    for i in l:
        r *= i
        if r > 1e18:
            break
    print(-1 if r > 1e18 else r)
### BUGGY CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = sorted(list(map(int, args[1].split())))
    F = sorted(list(map(int, args[2].split())), reverse=True)

    for _ in range(k):
        if A[-1] == 0:
            break

        max_af = 0
        max_i = -1

        for i in range(n):
            af = A[i]*F[i]
            if max_af < af:
                max_i = i
                max_af = af

        A[max_i] -= 1
        A.sort()

    ret = 0
    for i in range(n):
        ret = max(ret, A[i]*F[i])

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().split('\n'))))


### FIXED CODE ###

# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = np.array(sorted(list(map(int, args[1].split()))))
    F = np.array(sorted(list(map(int, args[2].split())), reverse=True))

    right = 1+A[-1]*F[0]
    left = -1

    total = A.sum()
    while left+1 < right:
        mid = (left+right)//2
        if total - np.minimum(A, mid//F).sum() <= k:
            right = mid
        else:
            left = mid

    return str(right)


if __name__ == "__main__":
    print(solve(*(open(0).read().split('\n'))))
### BUGGY CODE ###


def main2():
    input()
    t = input()
    pat = []
    for i in range(len(t)):
        if t[i] == 'R':
            pat.append(0)
        if t[i] == 'G':
            pat.append(1)
        if t[i] == 'B':
            pat.append(2)
    count = 0
    for i in range(len(pat)):
        for j in range(i + 1, len(pat)):
            for k in range(j + 1, len(pat)):
                tmp = {pat[i], pat[k], pat[j]}
                if j - i != k - j and len(tmp) == 3:
                    count += 1
    print(count)


if __name__ == '__main__':
    main2()

### FIXED CODE ###

def main3():
    n = int(input())
    s = input()

    ans = s.count("R") * s.count("B") * s.count("G")
    for i in range(n):
        for j in range(i, n):
            k = 2 * j - i
            if k >= n: break
            if s[i] != s[j] and s[j] != s[k] and s[i] != s[k]:
                ans -= 1

    print(ans)

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

def f(s):
    rd = [[10, 11, 12], [3, 6, 9], [4, 8, 12], [1, 2, 3], [4, 7, 10], [1, 5, 9]]
    k = len(s)
    md = 10 ** 9 + 7
    dp = [0] * 13
    dp[0] = 1
    for i, c in enumerate(s[::-1]):
        if c == "?":
            r1, r2, r3 = rd[i % 6]
            sm = sum(dp)
            dp=[(sm - (dp[j - r1] + dp[j - r2] + dp[j - r3])) % md for j in range(13)]
        else:
            m = int(c) * 10 ** i % 13
            dp=[dp[j - m] for j in range(13)]
    print(dp[5])

s = input()
f(s)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

    def __str__(self):
        return str(self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10 ** 9 + 7

def main():
    s = SI()
    n = len(s)
    dp = [[0] * 13 for _ in range(n + 1)]
    # dp[i][m]...iケタ目までみたときに、余りがmになる数の個数
    dp[0][0] = mint(1)
    e10 = 1
    for i, c in enumerate(s[::-1]):
        for m in range(13):
            pre = dp[i][m]
            if pre == 0: continue
            if c == "?":
                for d in range(10):
                    nm = (m + d * e10) % 13
                    dp[i + 1][nm] += pre
            else:
                nm = (m + int(c) * e10) % 13
                dp[i + 1][nm] += pre
        e10 = e10 * 10 % 13
    print(dp[n][5])

main()
### BUGGY CODE ###

n = int(input())

S = [0]
for i,s in enumerate(input().split()):
    S.append(int(s)+S[i])
    
count = 0
for i in range(n+1):
    count += S[i+1:].count(S[i])
print(count)

### FIXED CODE ###

n = int(input())

S = [0]
for i,s in enumerate(input().split()):
    S.append(int(s)+S[i])
S.sort()
S.append(10000000000)
count = 0
p = S[0]
l = 0
for i in range(n+2):
    if p != S[i]:
        count += (i-l)*(i-l-1)//2
        l = i
        p = S[i]
print(count)
### BUGGY CODE ###

import itertools
n = int(input())

ans = [0] * n
for v in itertools.product(list(range(1,n+1)), repeat=3):
    x,y,z = v[0], v[1], v[2]
    a = x*x + y*y + z*z + x*y + y*z + z*x
    if a <= n:ans[a-1] += 1
    else: continue
for i in ans: print(i)

### FIXED CODE ###

n = int(input())
ans = [0] * n
for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            a = x * x + y * y + z * z + x * y + x * z + y * z
            if a > n: continue
            ans[a-1] += 1
for i in ans: print(i)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
A = sorted(inpl())
B = sorted(inpl())
C = sorted(inpl())
cnt = [0] * n
res = 0
for i,b in enumerate(B):
    c = bisect.bisect_left(C,b+1)
    cnt[i] = n-c

acc = [0]
for x in cnt:
    acc += [acc[-1] + x]

for i,a in enumerate(A):
    c = bisect.bisect_left(B,a+1)
    res += sum(cnt) - acc[c]
print(res)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
A = sorted(inpl())
B = sorted(inpl())
C = sorted(inpl())
cnt = [0] * n
res = 0
for i,b in enumerate(B):
    c = bisect.bisect_left(C,b+1)
    cnt[i] = n-c

acc = [0]
for x in cnt:
    acc += [acc[-1] + x]
su = sum(cnt) 
for i,a in enumerate(A):
    c = bisect.bisect_left(B,a+1)
    res += su - acc[c]
print(res)
### BUGGY CODE ###

n = int(input())

for i in range(1, n + 1):
  count = 0
  # x <= y <= zとして考える
  if i >= 6:
    for x in range(1, i // 6 + 1):
      for y in range(x, i + 1):
        for z in range(y , i + 1):
          if x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x == i:
            if x == y:
              if y == z:
                count += 1
              else:
                count += 3
            else:
              if y == z:
                count += 3
              else:
                count += 6
  print(count)

### FIXED CODE ###

ans = [0] * 10000
for x in range(1, 101):
  for y in range(1, 101):
    for z in range(1, 101):
      k = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
      if k > 10000:
        break
      ans[k - 1] += 1

n = int(input())
for i in range(n):
  print(ans[i])
### BUGGY CODE ###


import scipy.linalg as linalg

N = int(input())
solve_arr = [int(i) for i in input().split()]
solve_arr = [i*2 for i in solve_arr]
w_arr = []

for i in range(N):
  arr = [0]*N
  if i == N-1:
    arr[i] = 1
    arr[0] = 1
  else:
    arr[i] = 1
    arr[i+1] = 1
  w_arr.append(arr)
  
LU = linalg.lu_factor(w_arr)
ans = linalg.lu_solve(LU, solve_arr)


for i in ans:
  print(str(int(i)) + " ", end ="")

### FIXED CODE ###

N = int(input())
dam_arr = list(map(int,input().split()))
mount_arr = []

# calculate 1st mount's rain
rain = 0
for i in range(N):
  if i%2==0:
    rain += dam_arr[i]
  else:
    rain -= dam_arr[i]
    
mount_arr.append(rain)

# caluculate others
for i in range(N-1):
  mount_arr.append(2*dam_arr[i]-mount_arr[-1])

mount_arr=[str(a) for a in mount_arr]
mount_arr=" ".join(mount_arr)
print(mount_arr)
### BUGGY CODE ###

import sys
input =sys.stdin.readline

N=int(input().rstrip('\n'))
s = []
for _ in range(N):
  A,B = (int(x) for x in input().rstrip('\n').split())
  s.append([A,B])
m = sorted(list(set(x[1] for x in s)))
used = 0
check = 0
for i in m:
  xs = [x for x in s if x[1]==i]
  used += sum([x[0] for x in xs]) 
  if used > i:
    check += 1
    print('No')
    break
if check == 0:
  print('Yes')

### FIXED CODE ###

import sys
input =sys.stdin.readline

N=int(input().rstrip('\n'))
s = {}
for _ in range(N):
  A,B = (int(x) for x in input().rstrip('\n').split())
  if B in s:
    s[B] += A
  else:
    s[B] = A
m = sorted(list(set(s)))
check = 0
used = 0
for i in m:
  used += s[i]
  if used > i:
    check += 1
    print('No')
    break
if check == 0:
  print('Yes')
### BUGGY CODE ###

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

a.sort()
b=list(set(a))
c=0
for i in range(len(b)):  
  if a.count( b[i] ) != b[i]:
    er = a.count( b[i] ) - b[i]
    if er<0:
      er = a.count( b[i] )
    if er>0:
      for j in range(er):
        a.remove( b[i] )
        c+=1
print(c)



### FIXED CODE ###

from collections import Counter

n=int(input())
a=list(map(int,input().split()))
counter=Counter(a)
b=list(set(a))
c=0
for i in b:
    k =  counter[i]
    c+= k-i if k-i>=0 else k
print(c)
### BUGGY CODE ###

n = int(input())
s = [0] * n
li = []
ans = []
for i in range(n):
    s[i] = input()
    if s[i] in ans:
        li[ans.index(s[i])][1] += 1
    else:
        li.append([s[i], 1])
        ans.append(s[i])
              
li.sort(key = lambda x: x[0])
li.sort(key = lambda x: x[1] , reverse = True)

a = li[0][1]
for j in range(len(ans)):
    if a == li[j][1]:
        print(li[j][0])
    else:
        break

### FIXED CODE ###

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

dic = {}
for i in range(n):
    if s[i] in dic:
        dic[s[i]] += 1
    else:
        dic[s[i]] = 1

max_dic = max(dic.values())
ans = [i for i, j in dic.items() if j == max_dic]
ans.sort()

for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

def main():
  n = int(input())
  s = input()
  r = []
  g = []
  b = []
  for i in range(n):
    if s[i]=="R":
      r.append(i)
    if s[i]=="G":
      g.append(i)
    if s[i]=="B":
      b.append(i)
  ans = 0
  for i in r:
    for j in g:
      for k in b:
        l = sorted([i,j,k])
        if l[1]-l[0] != l[2]-l[1]:
          ans += 1
  print(ans)
main()

### FIXED CODE ###

def main():
  n = int(input())
  s = input()
  ans = s.count("R")*s.count("G")*s.count("B")
  for i in range(n-2):
    for j in range(i+1,n-1):
      k = j + j - i
      if k >= n:
        break
      elif s[i] != s[j] and s[i] != s[k] and s[k] != s[j]:
        ans -=1
  print(ans)
main()
### BUGGY CODE ###

from bisect import *

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
A = reads()
B = reads()

D = 28
xor = 0
for d in range(D + 1):
  mask = (1 << (d + 1)) - 1 # [1] * (d+1)
  BB = sorted(x & mask for x in B)
  count = 0
  for a in (x & mask for x in A):
    count ^= bisect_left(BB, (1 << (d + 1)) - a) - bisect_left(BB, (1 << d) - a)
    count ^= bisect_left(BB, (1 << (d + 2)) - a) - bisect_left(BB, (1 << d) + (1 << (d + 1)) - a)
  if count & 1:
    xor |= 1 << d

print(xor)



### FIXED CODE ###

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]
 
N = read()
A = reads()
B = reads()
 
D = 28
xor = 0
for d in range(D + 1):
  mask = (1 << (d + 1)) - 1 # [1] * (d+1)
  AA = sorted(x & mask for x in A)
  BB = sorted(x & mask for x in B)
  count = 0
  itr = [N] * 4
  for a in AA:
    vs = [
      (1 << d) - a,
      (1 << (d + 1)) - a,
      (1 << d) + (1 << (d + 1)) - a,
      (1 << (d + 2)) - a
    ]
    for i in range(4):
      while 0 < itr[i] and vs[i] <= BB[itr[i]-1]:
        itr[i] -= 1
    count += (itr[1] - itr[0]) + (itr[3] - itr[2])
  if count & 1:
    xor |= 1 << d
 
print(xor)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
PATH = [[] for _ in range(N + 1)]
MOD = 10 ** 9 + 7

for _ in range(N - 1):
    x, y = map(int, readline().split())
    PATH[x].append(y)
    PATH[y].append(x)


def dfs(x, parent, isBlack=True):
    ret = 1
    for v in PATH[x]:
        if v == parent:
            continue

        cnt = dfs(v, x, False)

        if not isBlack:
            cnt += dfs(v, x, True)

        ret *= cnt
        ret %= MOD

    ret %= MOD

    return ret


ans = dfs(1, -1, True) + dfs(1, -1, False)
ans %= MOD
print(ans)


### FIXED CODE ###

import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# TLE

N = int(readline())
PATH = [[] for _ in range(N + 1)]
MOD = 10 ** 9 + 7

for _ in range(N - 1):
    x, y = map(int, readline().split())
    PATH[x].append(y)
    PATH[y].append(x)


dp = [[1] * 2 for _ in range(N+1)]


def dfs(x, parent):
    for v in PATH[x]:
        if v == parent:
            continue
        dfs(v, x)

        dp[x][0] *= (dp[v][0] + dp[v][1])
        dp[x][0] %= MOD
        dp[x][1] *= dp[v][0]
        dp[x][1] %= MOD

    return 0


dfs(1, -1)
ans = sum(dp[1])
ans %= MOD
print(ans)
### BUGGY CODE ###

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


b=[]

bb=[a[0]]
for k in range(1,len(a)):
    bb.append(a[k])
    bb=list(reversed(bb))

print(" ".join([str(x) for x in bb]))


### FIXED CODE ###

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

a.insert(0,-1)

m=len(a)-1
res=""

k=m
for i in range(int(m/2)+1):
    res+=str(a[k])+" "
    k-=2
    if k<=0:
        break

if m%2==0:
    s=1
else:
    s=2

if m>1:
    k=s
    for i in range(int(m/2)+1):
        res+=str(a[k])+" "
        k+=2
        if k>=m:
            break

print(res)
### BUGGY CODE ###

N = int(input())

my_list = [None] * N

for i in range(N):
    s_i = input()
    my_dict = {}
    for j in range(10):
        if s_i[j] in my_dict:
            my_dict[s_i[j]] += 1
        else:
            my_dict[s_i[j]] = 1
    my_dict = sorted(my_dict.items())
    my_list[i] = my_dict

sum = 0

for i in range(N):
    num = 0
    for j in range(i + 1, N):
        if my_list[i] == my_list[j]:
            num += 1
    sum += num

print(sum)


### FIXED CODE ###

n = int(input())
dict = {}
ans = 0

for i in range(n):
    s = str(sorted(input()))
    if s in dict.keys():
        ans += dict[s]
        dict[s] += 1
    else:
        dict[s] = 1
print(ans)