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

import sys
from collections import deque

class tree:
    def __init__(self):
        self.baby_list=deque()
        self.counter=0
    
    def add_value(self):
        for i in self.baby_list:
            hoge[i].counter+=self.counter
            hoge[i].add_value()
            
N,Q=list(map(int, input().split() ))

hoge={i:tree() for i in range(1,N+1)}
    
for i in range(N-1):
    a,b=list(map(int, input().split() ))
    hoge[a].baby_list.append(b)

for i in range(Q):
    root, value = list(map(int, input().split() ))
    hoge[root].counter+=value

hoge[1].add_value()
output = []
for t in hoge:
    output.append(hoge[t].counter)

    
output = list(map(str, output))
print(" ".join(output))

### FIXED CODE ###

import sys

sys.setrecursionlimit(10000000)


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

data={i+1:0 for i in range(N)}

# for i in range(N-1):
#     a,b=list(map(int, input().split() ))
#     hoge[a].baby_list.append(b)

relate = [list(map(int, input().split() )) for i in range(N-1)]
relate.sort(key=lambda x :x[0])
    
for i in range(Q):
    root, value = list(map(int, input().split() ))
    data[root]+=value

for a,b in relate:
    data[b]+=data[a]

print(" ".join(list(map(str,list(data.values())))))
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

count = 0
for r in range(N+1):
    for g in range(N+1):
        b = (N - R*r - G*g) / B
        if b >= 0 and b.is_integer():
            count += 1
print(count)

### FIXED CODE ###

R, G, B, N = map(int, input().split())

box = sorted([R,G,B],reverse=True)

count = 0
for x in range(0,N+1,box[0]):
    for y in range(0,N+1 - x ,box[1]):
        z = (N - x - y) / box[2]
        if z >= 0 and z.is_integer():
            count += 1
print(count)
### BUGGY CODE ###

from functools import reduce

MOD = 10**9 + 7

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
def lcm(a, b):
    return a // gcd(a, b) * b

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

lcmA = reduce(lcm, As)
#print('lcmA:', lcmA)

ans = 0
for A in As:
    ans += lcmA // A
    ans %= MOD

print(ans)


### FIXED CODE ###

from collections import Counter

def solve():
    MOD = 10**9 + 7
    maxA = 10**6

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

    isPrimes = [False]*2 + [True]*(maxA-1)
    minFs = [1] * (maxA+1)
    for i in range(2, int(maxA**0.5) + 1):
        if isPrimes[i]:
            for x in range(i*i, maxA+1, i):
                isPrimes[x] = False
                minFs[x] = i

    def getPrimeFactors(x):
        anss = []
        while minFs[x] > 1:
            anss.append(minFs[x])
            x //= minFs[x]
        if x != 1:
            anss.append(x)
        return anss

    PFss = []
    Primes = set()
    for A in As:
        PFs = getPrimeFactors(A)
        cnt = Counter(PFs)
        PFss.append(cnt)
        Primes |= cnt.keys()

    cntP = Counter()
    for PFs in PFss:
        for key, num in PFs.items():
            cntP[key] = max(cntP[key], num)

    lcmA = 1
    for key, num in cntP.items():
        lcmA *= pow(key, num, MOD)
        lcmA %= MOD

    def getInvs(n, MOD):
        invs = [1] * (n+1)
        for x in range(2, n+1):
            invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
        return invs

    invs = getInvs(10**6, MOD)

    ans = 0
    for A in As:
        ans += lcmA * invs[A]
        ans %= MOD

    print(ans)

solve()
### BUGGY CODE ###

a, b, c = map(int, input().split())
array = []
for i in range(c):
	array.append(int(input()))

point = [b] * a
 
for i in range(c):
	for j in range(len(point)):
		if j+1 != int(array[i]):
			point[j] = point[j] -1
            
for i in range(len(point)):
	if point[i] > 0:
		print('Yes')
	else:
		print('No')

### FIXED CODE ###

a, b, c = map(int, input().split())
array = []
for i in range(c):
	array.append(int(input()))

point = [b] * a
 
for i in range(c):
	point[array[i]-1] = point[array[i]-1] + 1
            
for i in range(len(point)):
	if (point[i]-c) > 0 :
		print('Yes')
	else:
		print('No')
### BUGGY CODE ###

n = int(input())
h = list(map(lambda x: int(x), input().split(" ")))

ans = []

for i in range(0,n):
	kari = 0
	for j in range(i,n-1):
		if h[j] < h[j+1]:
			break
		kari += 1
	ans.append(kari)

print(max(ans))

### FIXED CODE ###

n = int(input())
h = list(map(lambda x: int(x), input().split(" ")))

ans = 0

kari = 0
i = 0
for m in range(0,n-1):
	if h[m] >= h[m+1]:
		kari += 1
	else:
		kari = 0
	if ans < kari:
		ans = kari



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

from collections import Counter


MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


K = int(input())
S = input()
L = len(S)
modFacts, invs = prepare(K + L)

ans = 0
for n in range(L, L + K + 1):
    nonSi = (pow(25, n - L, MOD) * pow(26, L + K - n, MOD)) % MOD
    Si = (modFacts[n - 1] * invs[L - 1] * invs[n - 1 - (L - 1)]) % MOD
    ans += nonSi * Si
    ans %= MOD

print(ans)


### FIXED CODE ###

def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


MOD = 10 ** 9 + 7
K = int(input())
S = input()
L = len(S)
modFacts, invs = prepare(K + L)

ans = 0
for n in range(L, L + K + 1):
    nonSi = (pow(25, n - L, MOD) * pow(26, L + K - n, MOD)) % MOD
    Si = (modFacts[n - 1] * invs[L - 1] * invs[n - 1 - (L - 1)]) % MOD
    ans += nonSi * Si
    ans %= MOD

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

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

mod=10**9+7

def kaijo(n):
    result=1
    for i in range(2,n+1):
        result*=i
    if result>mod:
        result=result%mod
    return result
    
def count(n,m):
    return kaijo(n)*kaijo(m)

if n-m==-1 or n-m==1:
    result=count(n,m)
    amari=result%mod
    print amari
elif n-m==0:
    result=count(n,m)
    result*=2
    amari=result%mod
    print amari
else:
    print 0

### FIXED CODE ###

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

mod=10**9+7

def kaijo(n):
    result=1
    for i in range(2,n+1):
        result*=i
        if result>mod:
            result=result%mod
    return result
    
def count(n,m):
    return kaijo(n)*kaijo(m)

if n-m==-1 or n-m==1:
    result=count(n,m)
    amari=result%mod
    print amari
elif n-m==0:
    result=count(n,m)
    result*=2
    amari=result%mod
    print amari
else:
    print 0
### BUGGY CODE ###

r=lambda :map(int,input().split())
n,x=r()
*a,=r()
dp=[[0]*n for _ in range(n)]
for i,j in enumerate(a):
  dp[0][i]=j
for i in range(1,n):
  for j in range(n):
    dp[i][j]=min(dp[i-1][j],a[(j-i)%n])
print(min(i*x+sum(j) for i,j in enumerate(dp)))

### FIXED CODE ###

r=lambda :map(int,input().split())
n,x=r()
*a,=r()
dp=[[0]*n for _ in range(n)]
for i,j in enumerate(a):
  dp[0][i]=j
for i in range(1,n):
  for j in range(n):
    dp[i][j]=min(dp[i-1][j],a[(j-i)%n])
print(min(i*x+sum(j) for i,j in enumerate(dp)))
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
l_li=[]
r_li=[]
for i in range(q):
    l,r=map(int,input().split())
    l_li.append(l)
    r_li.append(r)
    
    
dp =[[0 for i in range(n+2)] for j in range(n+2)]

for i in range(n):
    for j in range(i,n):
        t=0
        if s[j]=="C" and j!=i:
            if s[j-1]=="A":
                t=1
        
        dp[i][j]=dp[i][j-1]+t
        
for i in range(q):
    print(dp[l_li[i]-1][r_li[i]-1])

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
    
dp =[0 for j in range(n)]


for j in range(n):
    t=0
    if s[j]=="C" and j!=0:
        if s[j-1]=="A":
            t=1

    dp[j]=dp[j-1]+t
        

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

N,M,K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# print("N=",N)
# print("M=",M)
# print("K=",K)
# print("A=",A)
# print("B=",B)

A_accumulate_cost = [0]
lastCost = 0
for i in range(N):
    lastCost += A[i]
    A_accumulate_cost.append(lastCost)
    if(lastCost > K):
        break

B_accumulate_cost = [0]
lastCost = 0
for i in range(M):
    lastCost += B[i]
    B_accumulate_cost.append(lastCost)
    if(lastCost > K):
        break

# print(A_accumulate_cost)
# print(B_accumulate_cost)

max_num = 0
for i in range(0,N+1):
    A_cost = A_accumulate_cost[i]
    if (A_cost > K):
        break

    for j in range(0,M+1):
        if (A_cost + B_accumulate_cost[j] > K):
            break

        if( i+j > max_num):
            max_num = i+j

print(max_num)

### FIXED CODE ###

N,M,K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_accumulate_cost = [0]
lastCost = 0
for i in range(N):
    lastCost += A[i]
    A_accumulate_cost.append(lastCost)

B_accumulate_cost = [0]
lastCost = 0
for i in range(M):
    lastCost += B[i]
    B_accumulate_cost.append(lastCost)

max_num = 0
p = M
for i in range(N+1):
    A_cost = A_accumulate_cost[i]
    if A_cost > K:
        break

    for j in range(p, -1, -1):
        if A_cost + B_accumulate_cost[j] <= K:
            p = j
            if i + j > max_num:
                max_num = i+j
            break

print(max_num)
### BUGGY CODE ###

h,n = map(int, input().split())
ab = []
amax = 10**5
for _ in range(n):
  ab.append(tuple(map(int,input().split())))
  amax = max(amax,ab[-1][1])
p = [10**10]*(h+amax+1)
q = [(i,j) for i,j in ab]
while q:
  a,b = q.pop()
  if b<p[a]: p[a]=b
  else: b=p[a]
  if a>=h: continue
  for i,j in ab:
    if b+j<p[a+i]:
      p[a+i]=b+j
      q.append((a+i,b+j))
print(min(p[h:]))

### FIXED CODE ###

h,n = map(int, input().split())
ab = []
amax = 10**5
for _ in range(n):
  ab.append(tuple(map(int,input().split())))
amax = max(a for a,b in ab)
p = [0]*(h+amax+1)
for i in range(1,h+amax):
  p[i] = min(p[i-a]+b for a,b in ab)
print(p[h])
### BUGGY CODE ###

s = input()
k = int(input())

d = set()

for i in range(len(s)):
    for j in range(i,len(s)):
        d.add(s[i:j + 1])
l = list(d)
l.sort()
# print(l)
if l[0] == '':
    l = l[1:]

print(l[k-1])


### FIXED CODE ###

s = input()

d = ["z"*5010]*5

k = int(input())
for i in range(len(s)):
    for j in range(i, i+k):
        x = s[i:j+1]
        if x in d or x == '':
            continue
        l = 0
        while l < 5 and x > d[l]:
            l += 1
        # print(k, d[0:k], x, d[k:])
        if l < 5:
            d = d[0:l] + [x] + d[l:]
            d = d[0:5]
        # print(f"->{d}")
# l = list(d)
# l.sort()
# print(l)
# if l[0] == '':
    # l = l[1:]

print(d[k-1])
### BUGGY CODE ###

N = int(input())
S = input()
min = N
i = 0
for i in range(N + 1):
    b = S[:i]
    f = S[i:]
    T = b.count('#') + f.count('.')
    if T < min:
        min = T

print(min)

### FIXED CODE ###

N = int(input())
S = input()
i = 0
b = S.count('.')
w = 0
min = b
for i in range(N):
    if S[i] == '#':
        w += 1
    else:
        b -= 1
    
    T = b + w
    if T < min:
        min = T

print(min)
### BUGGY CODE ###

N, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]
XY.sort()

def count(x_min, x_max, y_min, y_max, i, j):
    OK = 0
    NG = 0
    a = j - i + 1 - K
    for m in range(i, j + 1):
        if y_min <= XY[m][1] <= y_max:
            OK += 1
        else:
            NG += 1
        if OK >= K:
            return True
        if NG > a:
            return False


ans = 10 ** 20
for i in range(N - 1):
    for j in range(i + K - 1, N):
        for k in range(N):
            for l in range(N):
                if XY[k][1] < XY[l][1]:
                    if count(XY[i][0], XY[j][0], XY[k][1], XY[l][1], i, j):
                        # print ('A')
                        ans = min(ans, (XY[j][0] - XY[i][0]) * (XY[l][1] - XY[k][1]))
print (ans)


### FIXED CODE ###

#PythonだとTLEする
N, K = map(int, input().split())
X = [0] * N
Y = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    X[i] = x
    Y[i] = y

def count(x_min, x_max, y_min, y_max):
    cnt = 0
    for i in range(N):
        if x_min <= X[i] <= x_max and y_min <= Y[i] <= y_max:
            cnt += 1
    return cnt

ans = 10 ** 20
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                # print ('i, j , k, l = ', i, j, k, l)
                if X[i] < X[j] and Y[k] < Y[l]:
                    if count(X[i], X[j], Y[k], Y[l]) >= K:
                        # print ('A')
                        ans = min(ans, (X[j] - X[i]) * (Y[l] - Y[k]))
print (ans)
### BUGGY CODE ###

import heapq
[N,L] = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
A = []
for i,x in enumerate(B) : heapq.heappush(A,[x,i])
ANS = [None]*N
count = 0
for j in range(N):
    a = heapq.heappop(A)
    for i in range(L):
        try :
            if ANS[a[1]+i] == None :
                ANS[a[1]+i] = a[0]
                count += 1
        except IndexError : continue
    if count > N * 0.99 : break

for i in range(L):
    if ANS[i] == None : ANS[i] = min(B[:i+1])
for i in range(L,N):
    if ANS[i] == None : 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])
### BUGGY CODE ###

r,c,k=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(k)]
dp=[[[0 for _ in range(c+1)]for _ in range(r+1)]for _ in range(5)]
for x,y,z in a:
    dp[4][x][y]=z
for i in range(1,r+1):
    for j in range(1,c+1):
        v=dp[4][i][j]
        dp[0][i][j]=max(dp[0][i][j-1],dp[0][i-1][j],dp[1][i-1][j],dp[2][i-1][j],dp[3][i-1][j])
        dp[1][i][j]=max(dp[1][i][j-1],dp[0][i][j-1]+v,dp[0][i-1][j]+v,dp[1][i-1][j]+v,dp[2][i-1][j]+v,dp[3][i-1][j]+v)
        dp[2][i][j]=max(dp[2][i][j-1],dp[1][i][j-1]+v)
        dp[3][i][j]=max(dp[3][i][j-1],dp[2][i][j-1]+v)
print(max([dp[i][r][c] for i in range(4)]))

### FIXED CODE ###

r,c,k=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(k)]
dp=[[[0 for _ in range(c+1)]for _ in range(r+1)]for _ in range(5)]
for x,y,z in a:
    dp[4][x][y]=z
for i in range(1,r+1):
    for j in range(1,c+1):
        v=dp[4][i][j]
        dp[0][i][j]=max(dp[0][i][j-1],dp[0][i-1][j],dp[1][i-1][j],dp[2][i-1][j],dp[3][i-1][j])
        dp[1][i][j]=max(dp[1][i][j-1],dp[0][i][j-1]+v,dp[0][i-1][j]+v,dp[1][i-1][j]+v,dp[2][i-1][j]+v,dp[3][i-1][j]+v)
        dp[2][i][j]=max(dp[2][i][j-1],dp[1][i][j-1]+v)
        dp[3][i][j]=max(dp[3][i][j-1],dp[2][i][j-1]+v)
print(max([dp[i][r][c] for i in range(4)]))
### BUGGY CODE ###

import sys
import itertools as it

N = int(input()) 

def prime_judge(N):
    if N % 2 == 0 or N % 3 ==0:
        return False
    for i in range(4,N):
        if N % i == 0:
            return False
            break
    if N % 5 == 1 :
        return True
    else: False

a = []
n = 0
p = 2

while True:
    if prime_judge(p):
        if len(a) >= N:
            a_c = list(it.combinations(a, N-1))
            for a_p in a_c:
                a_p = list(a_p)
                a_p.append(p)
                a_p5 = list(it.combinations(a_p, 5))
                t_sum = 0
                for a_p5i in a_p5:
                    if not(prime_judge(sum(a_p5i))):
                        t_sum += 1
                if t_sum == len(a_p5):
                    a_p = list(a_p)
                    a2 = [str(i) for i in a_p]
                    print(" ".join(a2))
                    sys.exit()
        a.append(p)
    p += 1

### FIXED CODE ###

import sys

N = int(input()) 

def prime_judge(N):
    if N % 2 == 0 or N % 3 ==0:
        return False
    for i in range(4,N):
        if N % i == 0:
            return False
            break
    if N % 5 == 1 :
        return True
    else: False

a = []
n = 0
p = 2

while True:
    if prime_judge(p):
        if len(a) == N:
            a2 = [str(i) for i in a]
            print(" ".join(a2))
            sys.exit()
        a.append(p)
    p += 1
### BUGGY CODE ###

CH = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1,2,1]
N = int(input())
X = input()
s = 0
for x in X:
    if x == "1":
        s += 1
num = int(X,2)
num1 = num%(s+1)
if s > 1:
    num2 = num%(s-1)
for i in range(N):
    if int(X[i])==1:
        p = s-1
        if p == 0:
            print(0)
            continue
        x = (num2-2**(N-1-i))%p
        if x > 20:
            y = x%sum(map(int,list(bin(x))[2:]))
            print(2+CH[y])
        else:
            print(1+CH[x])
    else:
        p = s+1
        x = (num1+2**(N-1-i))%p
        if x > 20:
            y = x%sum(map(int,list(bin(x))[2:]))
            print(2+CH[y])
        else:
            print(1+CH[x])

### FIXED CODE ###

CH = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1,2,1]
N = int(input())
X = input()
s = 0
a = 1
A = []
B = []
for x in X:
    if x == "1":
        s += 1
for i in range(N):
    A.append(a)
    a = a*2 %(s+1)
a = 1
num = int(X,2)
num1 = num%(s+1)
if s > 1:
    num2 = num%(s-1)
    for i in range(N):
        B.append(a)
        a = a*2 %(s-1)
for i in range(N):
    if int(X[i])==1:
        p = s-1
        if p == 0:
            print(0)
            continue
        x = (num2-B[N-1-i])%p
        if x > 20:
            y = x%sum(map(int,list(bin(x))[2:]))
            print(2+CH[y])
        else:
            print(1+CH[x])
    else:
        p = s+1
        x = (num1+A[N-1-i])%p
        if x > 20:
            y = x%sum(map(int,list(bin(x))[2:]))
            print(2+CH[y])
        else:
            print(1+CH[x])
### BUGGY CODE ###

from itertools import product
from math import gcd

K = int(input())
print(sum([gcd(a,gcd(b,c)) for a,b,c in [i for i in product(range(1, K+1), repeat=3)]])) 


### FIXED CODE ###

from math import gcd

K = int(input())
ans = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            ans += gcd(a,gcd(b,c))
print(ans)
### BUGGY CODE ###

# seishin.py
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)

MOD = 10**9 + 7

def check(r, g, k):
    return (r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k])

# 左からk個置いた時、各色の最右の位置を持ってbfs
# r < g < b(= k) を維持して計算していく
que = [{} for i in range(N+1)]
que[0][0, 0] = 1
for k in range(N-1):
    cur = que[k]
    nxt = que[k+1]
    for key, val in cur.items():
        # r < g < b < k+1 の関係を元に次の状態に伝播
        r, g = key

        # 制約を満たす場合のみに伝播
        if check(g, k, k+1):
            nxt[g, k] = (nxt.get((g, k), 0) + val) % MOD
        if check(r, k, k+1):
            nxt[r, k] = (nxt.get((r, k), 0) + val) % MOD
        if check(r, g, k+1):
            nxt[r, g] = (nxt.get((r, g), 0) + val) % MOD
ans = 0
for key, val in que[N-1].items():
    r, g = key
    if check(g, N-1, N):
        ans += val
    if check(r, N-1, N):
        ans += val
    if check(r, g, N):
        ans += val
    ans %= MOD

print(ans)

### FIXED CODE ###

MOD = 10**9 + 7
N, M = map(int, input().split())
S = [[N]*(N+1) for i in [0,1,2]]
T = [[0]*(N+1) for i in [0,1,2]]

C = [0]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())
    S[x-1][r] = min(S[x-1][r], l)
    T[x-1][r] = max(T[x-1][r], l)
    C[r] = 1

S0, S1, S2 = S
T0, T1, T2 = T

ok = 1
for i in range(N+1):
    if not T2[i] < S1[i] or not T1[i] < S0[i]:
        ok = 0
        break

if not ok:
    print(0)
    exit(0)


X = {(0, 0): 3}
for b in range(1, N):
    t2 = T2[b+1]; s1 = S1[b+1]; t1 = T1[b+1]; s0 = S0[b+1]
    check = lambda r, g: t2 <= r < s1 and t1 <= g < s0

    Z = [0]*(N+1)
    if C[b+1]:
        if t1 <= b < s0:
            for (r, g), v in X.items():
                if t2 <= g < s1:
                    # r <- b+1
                    Z[g] += v
                if t2 <= r < s1:
                    # g <- b+1
                    Z[r] += v
        X = {(r, g): v for (r, g), v in X.items() if t2 <= r < s1 and t1 <= g < s0}
    else:
        Z = [0]*(N+1)
        for (r, g), v in X.items():
            # r <- b+1
            Z[g] += v
            # g <- b+1
            Z[r] += v;
    for z, v in enumerate(Z):
        if v:
            X[z, b] = v % MOD
print(sum(X.values()) % MOD)