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

a,b=input().split()
a=int(a)
b=int(b)
ll=[]
for i in range(b):
    c,d=input().split()
    c=int(c)
    d=int(d)
    for j in range(c,d+1):
        ll.append(j)
count=0
for i in range(1,a+1):
    k=ll.count(i)
    if k==b:
        count+=1
print(count)


### FIXED CODE ###

a,b=input().split()
a=int(a)
b=int(b)
ll=[]
l2=[]
for i in range(b):
    c,d=input().split()
    c=int(c)
    d=int(d)
    ll.append(c)
    l2.append(d)
x=max(ll)
y=min(l2)
z=y-x
if z>=0:
    print(z+1)
else:
    print(0)
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
for i in range(q):
    l,r=map(int,input().split())
    ans=0
    for i in range(l-1,r-1):
        if s[i]=="A" and s[i+1]=='C':
            ans+=1
    print(ans)

### FIXED CODE ###

n,q=map(int,input().split())
s=input()

ac_count=[]
ac=0

for i in range(n-1):
    if s[i:i+2]=='AC':
        ac+=1
    ac_count.append(ac)
    
for i in range(q):
    l,r=map(int,input().split())
    if l==1:
        print(ac_count[r-2])
    else:
        print(ac_count[r-2]-ac_count[l-2])
### BUGGY CODE ###

from collections import deque

N=int(input())
A=deque(list(map(int,input().split(" "))))


import fractions
from functools import reduce

ans=0
proc=lambda x: reduce(fractions.gcd, x)
GCD_target=proc(A)
#print("GCD_target = {}".format(GCD_target))

for i in range(N):
   #copied_A = A[:]
   remove=A.popleft()
   
   GCD_current= proc(A) #gcd_list(list(A))
   A.append(remove)
   #print(GCD_current)
   ans=max(ans,GCD_current)

print(ans)




### FIXED CODE ###

from fractions import *
n = int(input())
a = [0]+list(map(int, input().split()))+[0]
b = [0]*(n+2)
c = [0]*(n+2)
for i in range(1, n+1):
	b[i] = gcd(b[i-1], a[i])
for i in range(n, 0, -1):
	c[i] = gcd(c[i+1], a[i])

ans=1
for i in range(1, n+1):
    x1 = b[i-1]
    x2 = c[i+1]
    ans=max(ans, gcd(x1, x2))

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

# -*- coding: utf-8 -*-
from itertools import combinations
from collections import Counter
import math

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
#-----

A_cnt = Counter(A_list)

A_sum_of_combination={}
A_sum_of_combination_minus1={}
for k,v in A_cnt.items():
    # 個数2で場合分け
    if v >= 2:
        A_sum_of_combination[k] = math.factorial(v) // (math.factorial(v - 2) * math.factorial(2))
    else:
        A_sum_of_combination[k] = 0
    
    if (v-1) >= 2:
        A_sum_of_combination_minus1[k] = math.factorial(v-1) // (math.factorial((v-1) - 2) * math.factorial(2))
    else:
        A_sum_of_combination_minus1[k] = 0

sum_all = sum( [ v for k,v in A_sum_of_combination.items()] )

for i in A_list:
    num_selected = A_cnt[i] - 1
    
    if num_selected >= 2:
        ans = sum_all - A_sum_of_combination[i] + A_sum_of_combination_minus1[i]
        print(ans)
    else:
        ans = sum_all - A_sum_of_combination[i]
        print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import combinations
from collections import Counter
import math

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
#-----

A_cnt = Counter(A_list)

A_sum_of_combination={}
A_sum_of_combination_minus1={}
for k,v in A_cnt.items():
    # 個数2で場合分け
    if v >= 2:
        tmp_sum=1
        for i in range(2):
            tmp_sum *= (v-i)/(i+1)
        
        A_sum_of_combination[k] = int(tmp_sum)
        
    else:
        A_sum_of_combination[k] = 0
    
    if (v-1) >= 2:
        tmp_sum=1
        for i in range(2):
            tmp_sum *= ((v-1)-i)/(i+1)
        
        A_sum_of_combination_minus1[k] = int(tmp_sum)
        
    else:
        A_sum_of_combination_minus1[k] = 0

sum_all = sum( [ v for k,v in A_sum_of_combination.items()] )

for i in A_list:
    num_selected = A_cnt[i] - 1
    
    if num_selected >= 2:
        ans = sum_all - A_sum_of_combination[i] + A_sum_of_combination_minus1[i]
        print(ans)
    else:
        ans = sum_all - A_sum_of_combination[i]
        print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in a:
    ans *= i
print("-1" if ans>10**18 else ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = 1
if 0 in a:
    print(0)
    exit()
for i in a:
    ans *= i
    if ans > 10**18:
        print("-1")
        exit()
print(ans)
### BUGGY CODE ###

"""
"""
from math import factorial
from collections import defaultdict


def int_as_array(num): return list(map(int, [y for y in str(num)]))


def array_as_int(arr): return int(''.join(map(str, arr)))


def read_int(): return int(input())


def read_array(): return list(map(int, input().split(' ')))


def array_to_string(arr, sep=' '): return sep.join(map(str, arr))


def matrix_to_string(arr, sep=' '): return '[\n' + '\n'.join(
    [sep.join(map(str, row)) for row in arr]) + '\n]'


cache = {}


def fac(x):
    if cache.get(x) is not None:
        return cache[x]
    ans = factorial(x)
    cache[x] = ans
    return ans


def choose_combination(n, r):
    if r > n:
        return 0
    return int((fac(n) / fac((n - r))) * (1 / fac(r)))


def solve(n, array):
    counts = defaultdict(int)
    for x in array:
        counts[x] += 1
    ways_cache = {}
    for k in array:
        if ways_cache.get(k) is not None:
            print(ways_cache[k])
            continue
        ways = 0
        for x, count in counts.items():
            adjusted_count = counts[x]
            if x == k:
                adjusted_count -= 1
            ways += choose_combination(adjusted_count, 2)
        ways_cache[k] = ways
        print(ways)


N = read_int()
array = read_array()
solve(N, array)


### FIXED CODE ###

"""
"""
from math import factorial
from collections import defaultdict


def int_as_array(num): return list(map(int, [y for y in str(num)]))


def array_as_int(arr): return int(''.join(map(str, arr)))


def read_int(): return int(input())


def read_array(): return list(map(int, input().split(' ')))


def array_to_string(arr, sep=' '): return sep.join(map(str, arr))


def matrix_to_string(arr, sep=' '): return '[\n' + '\n'.join(
    [sep.join(map(str, row)) for row in arr]) + '\n]'


cache = {}


def fac(x):
    return factorial(x)


def choose_combination(n, r):
    if r > n:
        return 0
    # return int((fac(n) / fac((n - r))) * (1 / fac(r)))
    # return (fac(n) // fac((n - 2)) * (1 / 2))
    # return fac((n // n - 2)) * (1 / 2))
    return (n * (n-1)) // 2


def solve(n, array):
    counts = defaultdict(int)
    for x in array:
        counts[x] += 1
    total_ways = 0
    for x, count in counts.items():
        total_ways += choose_combination(counts[x], 2)
    for k in array:
        ways = choose_combination(counts[k] - 1, 2)
        print(total_ways + ways - choose_combination(counts[k], 2))


N = read_int()
array = read_array()
solve(N, array)
### BUGGY CODE ###

n = int(input())
goods = []
for _ in range(n):
  s = input()
  if not(s in goods):
    goods.append(s)
print(len(goods))

### FIXED CODE ###

n = int(input())
goods = []
for _ in range(n):
  s = input()
  goods.append(s)
goods = set(goods)
print(len(goods))
### BUGGY CODE ###

# import numpy as np
import math
import sys
input = sys.stdin.readline

X = int(input())

if X == 2:
    print(X)
    sys.exit()

if X % 2 == 0:
    X += 1

while True:
    isNotPrime = False
    temp = pow(2,X-1,X)
    if temp == 1:
        for i in range(2,int(math.sqrt(X)+1)):
            if X % i == 0:
                isNotPrime = True
            if isNotPrime:
                break
        if isNotPrime == False:
            break
    else:
        X += 2

print(X)


### FIXED CODE ###

# import numpy as np
import math
import sys
input = sys.stdin.readline

X = int(input())

if X == 2:
    print(X)
    sys.exit()

def segment_sieve(a,b):
    ass = []
    is_prime_small = [True] * (int(b**0.5)+1)
    is_prime = [True] * (b-a)
    for i in range(2,int(b**0.5)):
        if is_prime_small[i]:
            j = 2*i
            while j**2 < b:
                is_prime_small[j] = False
                j += i
            j = max(2*i,((a+i-1)//i)*i)
            while j < b:
                is_prime[j-a] = False
                j += i
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(a+i)
    if ass[0] == 1:
        del ass[0]
    return ass

list = segment_sieve(X,100004)
res = list[0]

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

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

DP = [[0] * (W + 1) for _ in range(N+1)]

for i in range(1, N+1):
    w, v = map(int, input().split())
    for j in range(1, W+1):
        DP[i][j] = max(DP[i][j-1], DP[i-1][j])
        if j - w >= 0:
            DP[i][j] = max(DP[i][j], DP[i-1][j-w] + v)

print(DP[N][W])


### FIXED CODE ###

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

DP = [[0] * (W + 1) for _ in range(N+1)]

for i in range(1, N+1):
    w, v = map(int, input().split())
    for j in range(1, W+1):
        DP[i][j] = max(DP[i][j-1], DP[i-1][j])
        if j - w >= 0:
            DP[i][j] = max(DP[i][j], DP[i-1][j-w] + v)

print(DP[N][W])
### BUGGY CODE ###

S=input()
l=len(S)
t=0
p=0
mm=[[0] * l for i in range(10)]

for i in range(10):
    for j in range(l):
        mm[i][j]=i*(10**j)%2019




for i in range(l-1,2,-1):

    p=0
    for j in range(i+1):


        p=(p+mm[int(S[i-j])][j])%2019

        if p==0:

            t+=1

print(t)


### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

N = int(input())
A=list(map(int,input().split()))
#print(A)

for i in range(N):
    count=0
    for j in range(N):
        
        for k in range(j,N):
            if i==j:
                continue
            elif j==k or i==k:
                continue
            #print(A[j],A[k])
            if A[j]==A[k]:
                count+=1
            else:
                pass
    print(count)


### FIXED CODE ###

from collections import Counter
N = int(input())
A=list(map(int,input().split()))
B=Counter(A)
tmp=0
for i in B.values():
    tmp+=int(0.5*(i)*(i-1))
    #print(tmp)
for i in A:            
    print(tmp-B[i]+1)
### BUGGY CODE ###

N = int(input())

gift_list = []
for _ in range(N):
  S = input()
  if not S in gift_list:
    gift_list.append(S)

print(len(gift_list))


### FIXED CODE ###

N = int(input())

S = set([input() for _ in range(N)])

print(len(S))
### BUGGY CODE ###

import sys

from decimal import Decimal

sys.setrecursionlimit(200000)


def solve(n, d, x):
    ans = 0
    while n:
        ans += d + (2 * n - 1) * x / 2
        d = ((n + 1) * d + 5 * x / 2) / n
        x *= (n + 2) / n
        n -= 1
    return ans


print(solve(*map(Decimal, input().split())))


### FIXED CODE ###

def solve(n, d, x):
    ans = 0
    while n:
        ans += d + (2 * n - 1) * x / 2
        d = ((n + 1) * d + 5 * x / 2) / n
        x *= (n + 2) / n
        n -= 1
    return ans


print('{:.10f}'.format(solve(*map(float, input().split()))))
### BUGGY CODE ###

#!/usr/bin/env python3

N, K = map(int, input().split())
H = list(map(int, input().split()))

if N <=K:
    print(abs(H[0]-H[-1]))
    exit()


dp = [float('inf') for _ in range(N+K+1)]

dp[0] = 0

for i in range(1, K+1):
    dp[i] = abs(H[0] - H[i])

for i in range(N):
    for j in range(i+1, i+K+1):
        if j < N:
            dp[j] = min(dp[i] + abs(H[i]-H[j]), dp[j])

print(dp[N-1])



### FIXED CODE ###

#!/usr/bin/env python3
N, K = map(int, input().split())
H = list(map(int, input().split()))

dp = [float('inf') for i in range(N+K+1)]


if K>=N:
    print(abs(H[0]-H[-1]))
    exit()


dp[0] = 0
for i in range(1, K+1):
    dp[i] = abs(H[i]-H[0])


for i in range(0, N):
    for j in range(i+1, i+K+1):
        if j < N:
            dp[j] = min(dp[i] + abs(H[i] - H[j]), dp[j])
print(dp[N-1])
### BUGGY CODE ###

N, C = list(map(int, input().split()))
tmax = 0
stc = [0 for _ in range(N)]
for i in range(N):
    stc[i] = list(map(int, input().split()))
    if stc[i][1] > tmax:
        tmax = stc[i][1]

c_timeline = [[0 for _ in range(C)] for _ in range(2*tmax + 1)]
for Si, Ti, Ci in stc:
    for j in range(2*Si-1, 2*Ti+1):
        c_timeline[j][Ci-1] = 1

rokuga = 0
for timeline in c_timeline:
    time = sum(timeline)
    if rokuga < time:
        rokuga = time

print(rokuga)


### FIXED CODE ###

N, C = list(map(int, input().split()))
tmax = 0
s = [0 for _ in range(N)]
t = [0 for _ in range(N)]
c = [0 for _ in range(N)]
for i in range(N):
    s[i], t[i], c[i] = list(map(int, input().split()))

tmax = max(t)
c_timeline = [[0]*C for _ in range(2 * tmax + 1)]
for i in range(N):
    S = s[i]
    T = t[i]
    channel = c[i] - 1
    for j in range(2 * S - 1, 2 * T + 1):
        c_timeline[j][channel] = 1

rokuga = 0
for timeline in c_timeline:
    time = sum(timeline)
    if rokuga < time:
        rokuga = time

print(rokuga)
### BUGGY CODE ###

#!/usr/bin/env python3
n = int(input())
a = list(map(int,input().split()))
ans = 0
for i in range(n):
  l = a.copy()
  l.pop(i)
  x = list(set(l.copy()))
  for j in range(len(x)):
    c = l.count(x[j])
    ans+=c*(c-1)//2
  print(ans)
  ans = 0

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0]*n
for i in range(n):
  b[a[i]-1]+=1
c = sum([i*(i-1)//2 for i in b])
for i in a :
  print(c-(b[i-1]-1))
### BUGGY CODE ###

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

mod=998244353

def invmod(x):
    return pow(x,mod-2,mod)

comb=1
pw=(M*pow(M-1,N-1,mod))%mod
ans=pw*comb
invmodm=invmod(M-1)

for k in range(1,K+1):
    pw*=invmodm
    comb*=(N-k)*invmod(k)
    ans=(ans+pw*comb)%mod

print(ans)

### FIXED CODE ###

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

mod=998244353

com=1
ans=0

for i in range(K+1):
    ans+=M*com*pow(M-1,N-1-i,mod)
    ans%=mod
    com*=(N-1-i)*pow(i+1,mod-2,mod)
    com%=mod

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

import collections
n=int(input())
s=input()
ans=0
d=collections.defaultdict(int)
for i in range(n):
  t=0
  for j in range(i,n):
    t+=(ord(s[j])-96)*(27**(j-i))
    if 0<d[t]<i and j-i+1>ans:
      ans=j-i+1
    elif d[t]==0 and i+2*(j-i+1)<=n:
      d[t]=j
    
print(ans)


### FIXED CODE ###

import collections
mod=10**9+7
base=257
n=int(input())
S=list(ord(s)-96 for s in input())
B=[0]*(n+1)
B[0]=1
for i in range(n):
  B[i+1]=(B[i]*base)%mod

def chk(x):
  ret=False
  h=0
  bx=B[x]
  d=collections.defaultdict(int)
  for i in range(x):
    h=(h*base+S[i])%mod
  d[h]=x
  for i in range(x,n):
    h=(h*base+S[i]-S[i-x]*bx)%mod
    if d[h]==0:
      d[h]=i+1
    elif d[h]<=i-x+1:
      ret=True
  return ret

l,r=0,n//2
while r-l>1:
  m=(l+r)//2
  if chk(m):
    l=m
  else:
    r=m
print(r if chk(r) else l)
### BUGGY CODE ###

n, m = map(int, input().split())
cards = {i for i in range(1,n+1)}
for _ in range(m):
    left, right = map(int, input().split())
    cards &= {i for i in range(left, right+1)}
print(len(cards))

### FIXED CODE ###

n, m = map(int, input().split())
left = []
right = []
for _ in range(m):
    l, r = map(int, input().split())
    left.append(l)
    right.append(r)
x = min(right) - max(left)
print(x+1) if x >=0 else print(0)
### BUGGY CODE ###

n,*s=map(str,open(0).read().split())
mydict={}
for i in set(s):
    mydict[i]=1
for i in range(int(n)):
    mydict[s[i]]+=1
    """
    if s[i] in mydict:
        mydict[s[i]]+=1
    else:
        mydict[s[i]]=1
    """
for i in sorted([kv[0] for kv in mydict.items() if kv[1]==max(mydict.values())]):
    print(i)

### FIXED CODE ###

n,*s=map(str,open(0).read().split())
mydict={}
for i in set(s):
    mydict[i]=1
for i in s:
    mydict[i]+=1
    """
    if s[i] in mydict:
        mydict[s[i]]+=1
    else:
        mydict[s[i]]=1
    """
v_max=max(mydict.values())
for i in sorted([kv[0] for kv in mydict.items() if kv[1]==v_max]):
    print(i)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
S = input()

R = []
G = []
B = []

for i in range(N):
  if S[i] == 'R':
    R.append(i)
  elif S[i] == 'G':
    G.append(i)
  else:
    B.append(i)

def count(X,Y,Z):
  count = 0
  for r in X:
    for g in Y:
      len_B = len(Z)
      if (r+g)%2==0 and (r+g)//2 in Z:
        len_B -= 1
      if 2*r-g in Z:
        len_B -= 1
      if 2*g-r in Z:
        len_B -= 1
      count += len_B
  return count

if len(R)>=max(len(G),len(B)):
  print(count(G,B,R))
elif len(G)>=len(R):
  print(count(R,B,G))
else:
  print(count(R,G,B))

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
S = input()

R = 0
G = 0
B = 0

for i in range(N):
  if S[i] == 'R':
    R += 1
  elif S[i] == 'G':
    G += 1
  else:
    B += 1
    
count = 0
for i in range(N-1):
  for j in range(i+1,N):
    if 2*j-i>=N:
      break
    if S[i]!=S[j] and S[2*j-i]!=S[i] and S[2*j-i]!=S[j]:
      count += 1

print(R*G*B-count)
### BUGGY CODE ###

#!/usr/bin/env python3
def main():
    S = input()

    ans = 0
    len_S = len(S)
    for i in range(len_S):
        for j in range(i + 1, len_S + 1):
            res = int(S[i:j])
            if res % 2019 == 0:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
def main():
    S = input()[::-1]

    counts = [0] * 2019
    counts[0] = 1
    res, digit = 0, 1
    for i in S:
        res += int(i) * digit
        res %= 2019
        digit *= 10
        digit %= 2019
        counts[res] += 1

    ans = 0
    for i in counts:
        ans += i * (i - 1) // 2
    print(ans)


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

from collections import defaultdict
n = int(input())
a = list(map(str,input().split()))
q = int(input())
d = defaultdict(lambda: 0)
for nums in a:
    d[nums] += 1
for i in range (q):
    Sum = 0
    b,c = map(str,input().split())
    d[c] += d[b]
    del d[b]
    for keys in d:
        cnt = d[keys]
        keys = int(keys)
        Sum += keys*cnt
    print(Sum)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
q = int(input())
d = defaultdict(lambda: 0)
Sum = 0
for nums in a:
    d[nums] += 1
for keys in d:
        cnt = d[keys]
        keys = int(keys)
        Sum += keys*cnt
for i in range (q):
    b,c = map(int,input().split())
    d[c] += d[b]
    Sum += (c-b)*d[b]
    del d[b]
    print(Sum)
### BUGGY CODE ###

import numpy as np
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

array = np.zeros(n+1)

for i in a:
    array[i] += 1

sum = 0
for i in array:
    if i > 1:
        sum += combinations_count(i, 2)

for i in a:
    tmp = sum
    if array[i] > 2:
        tmp -= (combinations_count(array[i],2) - combinations_count(array[i]-1, 2))
    elif array[i] == 2:
        tmp -= combinations_count(array[i], 2)
    elif array[i] == 1:
        tmp = tmp
    print(tmp)



### FIXED CODE ###

from collections import Counter

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

c = Counter(a)

total = 0
for i in c.items():
    x = i[1]
    total += x*(x-1)//2

for i in a:
    ans = total
    ans -= (c[i] - 1)
    print(ans)
### BUGGY CODE ###

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

for i in range(q):
  a.sort()
  b,c = map(int,input().split())
  for i in range(n):
    if a[i] == b:
      a[i] = c
    elif i > b:
      break
  print(sum(a))
  

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=sum(a)
q=int(input())
dp=[0]*(10**5+1)
for i in a:
  dp[i]+=1

for j in range(q):
  b,c=map(int,input().split())
  ans+=(c-b)*dp[b]
  dp[c]+=dp[b]
  dp[b]=0
  print(ans)
### BUGGY CODE ###

N = int(input())
H_list = input().split(" ")
max_count = 0

for i in range(0, N):
    S = int(H_list[i])
    count = 0
    for j in range(i + 1, N):
        if S >= int(H_list[j]):
            S = int(H_list[j])
            count += 1
        else:
            break
    if max_count < count:
        max_count = count

print(max_count)


### FIXED CODE ###

N = int(input())
H_LIST = input().split(" ")
H = []

for i in H_LIST:
    H.append(int(i))
   
count = 0
max_count = 0
for i in range(0, N-1):
    if H[i] >= H[i + 1]:
        count += 1
    else:
        count = 0 #メモリの動き
        
    if max_count < count:
        max_count = count


print(max_count)
### BUGGY 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)

### 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)