Harryxun/stf_run huggingface dataset:
N=int(input())
#頂点の色
colors=[0]*(N)
L=[[] for _ in range(N)]
for i in range(N-1):
  #u,vを長さwでつなぐ
  u,v,w=map(int, input().split())
  L[u-1].append((v-1,w,i))
  L[v-1].append((u-1,w,i))
  
def dfs(start_node, pre_node,is_even, ):
  for next_node,l,i in L[start_node]:
    if next_node==pre_node:
      continue
    if is_even:
      if l%2==0:
        colors[next_node]=0
      else:
        colors[next_node]=1
        is_even=False
    else:
      if l%2==0:
        colors[next_node]=1
      else:
        colors[next_node]=0
        is_even=True
    dfs(next_node, start_node, is_even)
    
dfs(0,-1,True)
for color in colors:
  print(color)

### FIXED CODE ###

import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()

edges = [[] for _ in range(N)]

for _ in range(N-1):
    u,v,w = imn()
    u -= 1
    v -= 1
    edges[u].append((v,w))
    edges[v].append((u,w))

colors = [None] * (N)

def set_color(vertex, color):
    colors[vertex] = color
    for v, w in edges[vertex]:
        if colors[v] == None:
            next_color = color
            if w % 2 == 1:
                next_color = (next_color+1)%2
            set_color(v, next_color)
set_color(0, 0)

for c in colors:
    print(c)
A = [list(map(int, input().split())) for _ in range(3)]
N = int(input())
for i in range(N):
  b = int(input())
  for j in range(3):
    for k in range(3):
      if A[j][k] == b:
        A[j][k] = "x"
if A[0] == ["x","x","x"]:
  print("Yes")
elif A[1] == ["x","x","x"]:
  print("Yes")
elif A[2] == ["x","x","x"]:
  print("Yes")
elif A[0][0] == "x" and A[1][0] == "x" and A[2][0] == "x":
  peint("Yes")
elif A[0][1] == "x" and A[1][1] == "x" and A[2][1] == "x":
  print("Yes")
elif A[0][2] == "x" and A[1][2] == "x" and A[2][2] == "x":
  print("Yes")
elif A[0][0] == "x" and A[1][1] == "x" and A[2][2] == "x":
  print("Yes")
elif A[0][2] == "x" and A[1][1] == "x" and A[2][0] == "x":
  print("Yes")
else:
  print("No")

### FIXED CODE ###

A = [list(map(int, input().split())) for _ in range(3)]
N = int(input())
for i in range(N):
  b = int(input())
  for j in range(3):
    for k in range(3):
      if A[j][k] == b:
        A[j][k] = "x"
      else:
        pass
if A[0] == ["x","x","x"]:
  print("Yes")
elif A[1] == ["x","x","x"]:
  print("Yes")
elif A[2] == ["x","x","x"]:
  print("Yes")
elif A[0][0] == "x" and A[1][0] == "x" and A[2][0] == "x":
  print("Yes")
elif A[0][1] == "x" and A[1][1] == "x" and A[2][1] == "x":
  print("Yes")
elif A[0][2] == "x" and A[1][2] == "x" and A[2][2] == "x":
  print("Yes")
elif A[0][0] == "x" and A[1][1] == "x" and A[2][2] == "x":
  print("Yes")
elif A[0][2] == "x" and A[1][1] == "x" and A[2][0] == "x":
  print("Yes")
else:
  print("No")
s1,s2,s3=input.split()
ans="".join([s1[0],s2[0],s3[0]])
print(ans.upper())

### FIXED CODE ###

s1,s2,s3=input().split()
ans="".join([s1[0],s2[0],s3[0]])
print(ans.upper())
a,b,c=map(int,input().split())
print(min(c-a+b,0)

### FIXED CODE ###

a,b,c=map(int,input().split())
print(max(c-a+b,0))
N,M = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
b = []
for i in range(M-1):
  b.append(a[i+1]-a[i])
b.sort()
if M == 1:
  print(0)
else:
  x = a[M-1]-a[0]
  y = M-2
  for i in range(N-1):
    x -= b[y]
    y -= 1
  print(x)

### FIXED CODE ###

N,M = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
b = []
for i in range(M-1):
  b.append(a[i+1]-a[i])
b.sort()
if N >= M:
  print(0)
else:
  x = a[M-1]-a[0]
  y = M-2
  for i in range(N-1):
    x -= b[y]
    y -= 1
  print(x)
n=int(input())
a = list(map(int, input().split()))
x=[]
for i in range(1,n+1):
    for t in range(n):
        if a[t]==i:
            num=t+1
            x.append(num)
for q in x:
    print(q,end=" ")

### FIXED CODE ###

n=int(input())
if n%2==0:
    print((n//2)/n)
else:
    x=((n+1)//2)/n
    print(x)
digits = input('')
digits = digits.split(' ')
average = math.round(int(digits[0]) + int(digits[1]) / 2)
print(average)

### FIXED CODE ###

import math

digits = input('')
digits = digits.split(' ')
average = math.ceil((int(digits[0]) + int(digits[1])) / 2)
print(average)
from collections import deque
n, k = map(int, input().split())
D = list(map(int, input().split()))

# 1. 初期化
ok_lst = [x for x in range(0, 10) if x not in D]
ok_lst.sort(reverse = True)
stack = deque([x for x in ok_lst if x != 0])

while len(stack) > 0:
    # 2. 現在の情報の取得
    # 今回は現在の数字
    now_num = stack.pop()
    # 3. 処理
    # もしnow_numの桁数がnの桁数と同じかつ条件の値以上の場合，ansに記録しwhileを終了．
    # もしnow_numの桁数がnの桁数と同じかつ条件の値未満の場合，次は数値を足すとまずいのでcontinueで防ぐ
    if len(str(now_num)) == len(str(n)) and now_num >= n:
        ans = now_num
        break
    if len(str(now_num)) == len(str(n)) and now_num < n:
        continue
    # 4. 更新
    for x in ok_lst:
        next_num = str(now_num) + str(x)
        next_num = int(next_num)
        stack.append(next_num)

print(ans)

### FIXED CODE ###

from collections import deque
n, k = map(int, input().split())
D = list(map(int, input().split()))
ok_lst = [x for x in range(0, 10) if x not in D]
stack = deque([x for x in ok_lst if x != 0])
while len(stack) > 0:
    now_num = stack.popleft()
    if now_num >= n:
        print(now_num)
        break
    for x in ok_lst:
        next_num = str(now_num) + str(x)
        stack.append(int(next_num))
n = int(input())

before_reverse_num = 0
for _ in range(n):
  before_reverse_num += 1 / int(input())
after_reverse_num = 1 / before_reverse_num
print(str(round(after_reverse_num,5)))

### FIXED CODE ###

n = int(input())
values = input().split()
before_reverse_num = 0
for _ in range(n):
  before_reverse_num += 1 / int(values[_])
after_reverse_num = 1 / before_reverse_num
print(str(round(after_reverse_num,5)))
import math
from matplotlib import pyplot
class Dot:
    x=0.0
    y=0.0
    def __init__(self,x,y):
        self.x=x
        self.y=y
    def __lt__(self,other):
        return self.x < other.x
    def print(self):
        x=self.x
        y=self.y
        print("{:.8f} {:.8f}".format(x,y))       
def kock(n,a,b,dots):
    if n == 0:
        return
    s=Dot((2*a.x+b.x)/3,(2*a.y+b.y)/3)
    t=Dot((a.x+2*b.x)/3,(a.y+2*b.y)/3)
    rad=math.radians(60)
    x=(t.x-s.x)*math.cos(rad)-(t.y-s.y)*math.sin(rad)+s.x
    y=(t.x-s.x)*math.sin(rad)+(t.y-s.y)*math.cos(rad)+s.y
    u=Dot(x,y)

    kock(n-1,a,s,dots)
    s.print()
    dots.append(s)
    kock(n-1,s,u,dots)
    u.print()
    dots.append(u)
    kock(n-1,u,t,dots)
    t.print()
    dots.append(t)
    kock(n-1,t,b,dots)

if __name__ == "__main__":
    n=int(input())
    dots=[]
    dot1=Dot(0,0)
    dot2=Dot(100,0)
    dots.append(dot1)
    dots.append(dot2)
    dot1.print()
    kock(n,dot1,dot2,dots)
    dot2.print()


### FIXED CODE ###

import math
class Dot:
    x=0.0
    y=0.0
    def __init__(self,x,y):
        self.x=x
        self.y=y
    def __lt__(self,other):
        return self.x < other.x
    def print(self):
        x=self.x
        y=self.y
        print("{:.8f} {:.8f}".format(x,y))       
def kock(n,a,b,dots):
    if n == 0:
        return
    s=Dot((2*a.x+b.x)/3,(2*a.y+b.y)/3)
    t=Dot((a.x+2*b.x)/3,(a.y+2*b.y)/3)
    rad=math.radians(60)
    x=(t.x-s.x)*math.cos(rad)-(t.y-s.y)*math.sin(rad)+s.x
    y=(t.x-s.x)*math.sin(rad)+(t.y-s.y)*math.cos(rad)+s.y
    u=Dot(x,y)

    kock(n-1,a,s,dots)
    s.print()
    dots.append(s)
    kock(n-1,s,u,dots)
    u.print()
    dots.append(u)
    kock(n-1,u,t,dots)
    t.print()
    dots.append(t)
    kock(n-1,t,b,dots)

if __name__ == "__main__":
    n=int(input())
    dots=[]
    dot1=Dot(0,0)
    dot2=Dot(100,0)
    dots.append(dot1)
    dots.append(dot2)
    dot1.print()
    kock(n,dot1,dot2,dots)
    dot2.print()
from sys import stdin
    n = int(stdin.readline())
    a = []
    for _ in xrange(n):
        s = stdin.readline().strip()
        di = {}
        for i in s:
            di[i] = di.get(i,0) + 1
        a.append(di)       
    ans = ''
    b = 'abcdefghijklmnopqrstuvwxyz'
    for i in b:
        x = 10**5
        for yy in a:
            x = min(x, yy.get(i,0))
        ans += x*i
    print ans    

### FIXED CODE ###

from sys import stdin
n = int(stdin.readline())
a = []
for _ in xrange(n):
    s = stdin.readline().strip()
    di = {}
    for i in s:
        di[i] = di.get(i,0) + 1
    a.append(di)       
ans = ''
b = 'abcdefghijklmnopqrstuvwxyz'
for i in b:
    x = 10**5
    for yy in a:
        x = min(x, yy.get(i,0))
    ans += x*i
print ans
from decimal import Decimal


def main():
    A, B = map(Decimalt,input().split())
    print(int(A*B))

if __name__ == '__main__':
    main()


### FIXED CODE ###

x,y = map(int,input().split())
print(x*y)
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=sorted(A)
C=[]
import bisect
a=bisect.bisect_left(B,0)
b=bisect.bisect_right(B,0)
x=a
y=b-a
z=N-x-y
if x*z<K<=N-(z*(z-1)+x*(x-1)):
  print(0)
elif K<=x*z:
  for i in range(x):
    for j in range(x+y,N):
      C.append(B[i]*B[j])
  print(sorted(C)[K-1])
else:
  for i in range(x-1):
    for j in range(i+1,x):
      C.append(B[i]*B[j])
  for i in range(x+y,N-1):
    for j in range(i+1,N):
      C.append(B[i]*B[j])
  D=sorted(C)
  e=N*(N-1)//2
  print(D[-1*(e)-1+K])

### FIXED CODE ###

N,K=map(int, input().split())
A=list(map(int, input().split()))
A=sorted(A)
import numpy as np
A=np.array(A,dtype="int64")
Z=A[A==0]
H=A[A<0]
S=A[A>0]
l,r=-10**19,10**19
while r-l>1:
  mid=(r+l)//2
  cnt=0
  cnt+=A.searchsorted(mid//S,side="right").sum()
  cnt+=(N-A.searchsorted((-mid-1)//(-H),side="right")).sum()
  cnt-=np.count_nonzero(A*A<=mid)
  if mid>=0:
    cnt+=len(Z)*N 
  cnt//=2
  if cnt>=K:
    r=mid
  else:
    l=mid 
print(r)
N=int(input())
M=int(input())
if N>M:
   print(N-M)
else:
   print(-1)

### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
B=0
for i in A:
    B=B+i       
N=N-B
if 0<=N:
    print(N)
else:
    print(-1)
import re
# 盤面の状態
s = input()

cnt = 0

while True:
    print(s)
    
    # 全部Wになるまで or 1文字残しまで繰り返す
    if s.count("W") == len(s):
        break

    # Bがどちらにあるか調べる
    if s[len(s)-1] == "B":
        # 逆向きにする
        s = s[::-1]
    else:
        # Bが末尾に見つからなければ、何もしない
        pass
        
    # 先頭を置換する
    if s[0] == "B":
        s = re.sub(r'[B]+', "", s,1)
        cnt +=1
    elif s[0] == "W":
        s = re.sub(r'[W]+', "", s,1)
        cnt +=1

print(cnt)

### FIXED CODE ###

import re
# 盤面の状態
s = input()

# Aマッチする数を数える
w = re.findall(r'[W]+', s)
# Bにマッチする数を数える
b= re.findall(r'[B]+', s)

# 全部Wなら入れ替える必要なし
if s.count("W") == len(s):
    print(0)
else:
    print(len(w)+len(b)-1)
import math

N = int(input())
x = math.factorial(N)

ans=1
for i in range(2, 1+int(x**(1/2))):
    cnt = 1
    while x%i == 0:
        x //= i
        cnt += 1
    ans *= cnt
                
print(ans%(10**9+7))

### FIXED CODE ###

import math

N = int(input())
x = math.factorial(N)

ans = 1
i = 2
while i <= x:
    cnt = 1
    while x%i == 0:
        x //= i
        cnt += 1
    ans *= cnt
    i += 1
                
print(ans%(10**9+7))
def search_max_gcd(M, possible):
    if (M % possible) == 0:
        return possible
    elif possible == 1:
        return 1
    else:
        return search_max_gcd(M, possible-1)

def main():
    N, M = map(int, input().split())
    first_possible = M//N
    print(search_max_gcd(M, first_possible))

main()

### FIXED CODE ###

from math import *

def main():
    N, M = map(int, input().split())
    if N==1:
        print(M)
        return
    special_value = M//N
    divisor_set = set(i for i in range(1, (int(sqrt(M)) + 1)) if (M % i == 0))
    divisor_set = divisor_set.union(M/j for j in divisor_set)
    print(int(max([i for i in divisor_set if special_value >= i])))
    return

main()
n = int(input)
count = 0
ans = 'No'
for i in range(n):
    a , b = map(int,input().split(' '))
    if a!=b:
        count = 0 
    else:
        count += 1
    if count == 3:
        ans = 'Yes'
print(ans)


### FIXED CODE ###

n = int(input())
count = 0
ans = 'No'
for i in range(n):
    a , b = map(int,input().split(' '))
    if a!=b:
        count = 0 
    else:
        count += 1
    if count == 3:
        ans = 'Yes'
print(ans)
import heapq as hq

X, Y, Z, K = map(int, 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()]

pri = []
data = []
hq.heapify(pri)

A.sort()
B.sort()
C.sort()
A.reverse()
B.reverse()
C.reverse()

hq.heappush(pri, [-A[0]-B[0]-C[0],0,0,0])
data.append([0,0,0])

for i in range(K):
    s = pri[0][1]
    t = pri[0][2]
    u = pri[0][3]
    if s+1 <= X-1:
        if [s + 1, t, u] not in data:
            data.append([s+1, t, u])
            hq.heappush(pri, [-A[s+1]-B[t]-C[u],s+1,t,u])
    if t+1 <= Y-1:
        if [s, t+1, u] not in data:
            data.append([s, t+1, u])
            hq.heappush(pri, [-A[s]-B[t+1]-C[u],s,t+1,u])
    if u+1 <= Z-1:
        if [s, t, u+1] not in data:
            data.append([s, t, u+1])
            hq.heappush(pri, [-A[s]-B[t]-C[u+1],s,t,u+1])
    print(hq.heappop(pri)[0] * -1)

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())

if (e - a) <= k:
    print("Yay!")
else:
    print(":(")
import heapq
[N,L] = [int(x) for x in input().split()]
A = [[int(x),int(i)] for i,x in enumerate(input().split())]
heapq.heapify(A)
ANS = [10**9+1]*N
count = 0
for j in range(N):
    a = heapq.heappop(A)
    for i in range(L):
        try :
            if ANS[a[1]+i] == 10**9+1 :
                ANS[a[1]+i] = a[0]
                count += 1
        except IndexError : continue
    if count + 1000 > N : break

for i in range(L):
    if ANS[i] == 10**9+1 : ANS[i] = min(B[:i+1])
for i in range(L,N):
    if ANS[i] == 10**9+1 : ANS[i] = min(B[i+1-L:i+1])

for i in ANS[L-1:-1]:
    print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
import copy
N, M = map(int, input().split())

def f(x):
    return int(x) - 1

A = []
#B = []
C = []
for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    #B.append(b)
    C.append(list(map(f, input().split())))



def rec(cost, still_closed, d):
    """
    初期値
    cost = 0
    still_closed = [1]*N
    d = 0
    """
    if sum(still_closed) == 0:
        return cost
    if d == M:
        return - 1
    still_closed1 = copy.copy(still_closed)
    still_closed2 = copy.copy(still_closed)
    res1 = rec(cost, still_closed1, d + 1)
    for c in C[d]:
        still_closed[c] = 0
    res2 = rec(cost + A[d], still_closed, d + 1)
    if res1 == - 1 or res2 == - 1:
        return max(res1, res2)
    else:
        return min(res1, res2)

print(rec(0, [1]*N, 0))

### FIXED CODE ###

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

INF = 10**7
dp = [INF]*2**N
dp[0] = 0

for i in range(M):
    a, b = map(int, input().split())
    d = sum((1<< (i - 1)) for i in  map(int, input().split()))    
    for j in range(2**N):
        jord = j | d
        dp[jord] = min(dp[j] + a, dp[jord])
        
if dp[- 1] == INF:
    print(- 1)
else:
    print(dp[- 1])
n,m=map(int,input().split())

par=[i for i in range(n)]

visited=[False]*n

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


def union(x,y):
  fx=find(x)
  fy=find(y)
  if fx!=fy:
    par[fx]=fy

ans=-1

for i in range(m):
  x,y,z=map(int,input().split())
  union(x-1,y-1)


ans={find(i) for i in range(n)}

print(len(ans))


### FIXED CODE ###

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

par=[i for i in range(n)]
size=[1]*n

def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def union(a,b):
  x=find(a)
  y=find(b)
  if x!=y:
    if size[x]<size[y]:
      par[x]=par[y]
      size[y]+=size[x]
    else: 
      par[y]=par[x]
      size[x]+=size[y]
  else:
    return

for i in range(m):
  x,y,z=map(int,input().split())
  union(x-1,y-1)


ans={find(i) for i in range(n)}

print(len(ans))
a,b = map(int, input().split())
print(max(a+b, a-b, a*b)

### FIXED CODE ###

a,b = map(int, input().split())
print(max(a+b, a-b, a*b))
import sys

values = [int(input()) for i in range(int(input()))]
maxv = - sys.maxsize - 1
minv = values[0]

for val in enumerate(values):
    maxv = max(maxv, (val - minv))
print(maxv)



### FIXED CODE ###

values = [int(input()) for _ in range(int(input()))]
maxv = values[1] - values[0]
minv = values[0]

for val in values[1:]:
    maxv = max(maxv, val - minv)
    minv = min(minv, val)         # 今までの最小値を保持(自分と自分を比較しない様に、最大値の評価後に計算)
print(maxv)
d = int(input())
if d = 25:
  print("Christmas")
elif d = 24:
  print("Christmas Eve")
elif d = 23:
  print("Christmas Eve Eve")
else:
  print("Christmas Eve Eve Eve")

### FIXED CODE ###

d = input()
if d == "25":
  print("Christmas")
elif d == "24":
  print("Christmas Eve")
elif d == "23":
  print("Christmas Eve Eve")
else:
  print("Christmas Eve Eve Eve")
import numpy as np
n = int(input())

if n == 1:
    print(1)
else:
    res_v = np.zeros(n + 1, dtype='int64')
    res_v_cumsum = np.zeros(n + 1, dtype='int64')
    res_v[0] = 0
    res_v[1] = 1
    res_v[2] = 1
    res_v_cumsum[0] = 0
    res_v_cumsum[1] = 1
    res_v_cumsum[2] = 2

    M = 1000000007

    for k in range(3, n):
        res_v[k] = (1 + res_v_cumsum[k-1] - res_v[k-2]) % M
        res_v_cumsum[k] = (res_v_cumsum[k-1] + res_v[k]) % M

    print((((res_v_cumsum[n-2] * (((n-1) * (n-1)) % M)) % M) + ((res_v_cumsum[n-1] * (n-1)) % M) + n + (n-1)*(n-1)%M) % M)

### FIXED CODE ###

n = int(input())

if n == 1:
    print(1)
else:
    res_v = [0]*(n + 1)
    res_v_cumsum = [0]*(n + 1)
    res_v[0] = 0
    res_v[1] = 1
    res_v[2] = 1
    res_v_cumsum[0] = 0
    res_v_cumsum[1] = 1
    res_v_cumsum[2] = 2

    M = 1000000007

    for k in range(3, n):
        res_v[k] = (1 + res_v_cumsum[k-1] - res_v[k-2]) % M
        res_v_cumsum[k] = (res_v_cumsum[k-1] + res_v[k]) % M
    #print(res_v)
    print((((res_v_cumsum[n-2] * (((n-1) * (n-1)) % M)) % M) + ((res_v_cumsum[n-1] * (n-1)) % M) + n + (n-1)*(n-1)%M) % M)
n, m = map(int, input().split())
p = []
for i in range(n):
  r, l = map(int, input().split())
  p.append((r, l))

p.sort()
mr = 0
c = 0
for l, r in p:
  if l >= mr:
    mr = r
    continue
  c += 1
  mr = min(mr, r)

print(c)

### FIXED CODE ###

n, m = map(int, input().split())
p = []
for i in range(m):
  r, l = map(int, input().split())
  p.append((r, l))

p.sort()
mr = 0
c = 0
for l, r in p:
  if l >= mr:
    mr = r
    c += 1
    continue
  mr = min(mr, r)

print(c)
h, w, d = map(int, input().split())
arr = [0] * (h * w + 1)

a = [list(map(int, input().split())) for _ in range(h)]

for i in range(h):
    for j in range(w):
        s = a[i][j]
        arr[s] = (i, j)

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

cnt = h * w
result = [[0] for _ in range(d)]
for i in range(d):
    l = i
    score = 0
    while l + d <= cnt:
        if l == 0:
            result[i].append(score)
            l += d
            continue
        (ux, uy) = arr[l]
        (vx, vy) = arr[l + d]
        score += (abs(vx - ux) + abs(vy - uy))
        result[i].append(score)
        l += d


for l, r in lr:
    ans = result[l % d]
    print(ans[r // d] - ans[l // d])

### FIXED CODE ###

n = int(input())
print(n // 3)
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
a_=a.sort(reverse=True)
b_=b.sort(reverse=True)
totl=0
for i in range(n):
  totl+=min(a_[i],b_[i])
print(totl)
  


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
cnt=0
for i in range(n):
  if b[i]-a[i]>0:
    cnt+=a[i]
    cnt+=min(b[i]-a[i],a[i+1])
    a[i+1]=max(a[i+1]-b[i]+a[i],0)
  else:
    cnt+=b[i]
print(cnt)
N, M = map(int,input().split()))
a = (N*(N-1))/2
b = (M*(M-1))/2
print(a+b

### FIXED CODE ###

N, M = map(int,input().split())
a = (N*(N-1))/2
b = (M*(M-1))/2
print(int(a+b))
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
mp = defaultdict(int)
for i in a:
    mp[i] += 1
q = int(input())
for _ in range(q):
    #print(mp)
    s = 0   
    b,c=map(int,input().split())
    if c in mp:
        mp[c] = mp[c]+mp[b]
        mp.pop(b)
    else:
        mp[c] = mp.pop(b)
    for i in mp:
        s += (mp[i])*i
    print(s)
    

### FIXED CODE ###

#D                 more faster method than above               see it ..........
l = lambda : list(map(int,input().strip().split()))
n = int(input())
a = l()
t = [0]*(10**5+1)
s = 0
for i in a:
    s += i
    t[i] += 1
q = int(input())
for _ in range(q):
    b,c = l()
    s += (c-b)*t[b]
    t[c] += t[b]
    t[b] = 0
    print(s)
S = int(input())
h = s // 3600
m = s % 3600 // 60
s = S % 60
print(h,m,s, sep=':')

### FIXED CODE ###

import sys
S = int(sys.stdin.readline())
h = int(S / 60 / 60)
m = int(S % 3600 / 60)
s = S % 60
print("%d:%d:%d" % (h, m, s))
n=int(input())
print(long(n*(n-1)/2)


### FIXED CODE ###

s=input()
t=input()
ans=0
for i in range(3):
    if s[i]==t[i]:
        ans+=1
print(ans)
import math

a, b = map(int, input().split())
print(a*b//math.gcd(a,b))


### FIXED CODE ###

import fractions

a, b = map(int, input().split())
print(a*b//fractions.gcd(a,b))
N=int(input())
for i in range(9):
  if (N%i)==0 and N/i<10:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

N=int(input())
if N%2==0 and N/2<10:
    print('Yes')
elif N%3==0 and N/3<10:
    print('Yes')
elif N%4==0 and N/4<10:
    print('Yes')
elif N%5==0 and N/5<10:
    print('Yes')
elif N%6==0 and N/6<10:
    print('Yes')
elif N%7==0 and N/7<10:
    print('Yes')
elif N%8==0 and N/8<10:
    print('Yes')
elif N%9==0 and N/9<10:
    print('Yes')
elif N==1:
    print('Yes')
else:
    print('No')