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

A, B, C, D = map(int,input().split())

d=[[0 for j in range(D-B+1)] for i in range(C-A+1)]
d[0][0]=1
for i in range(1,C-A+1):
  d[i][0] = B*d[i-1][0] % 998244353
for j in range(1,D-B+1):
  d[0][j] = A*d[0][j-1] % 998244353
  
for i in range(1,C-A+1):
  for j in range(1,D-B+1):
    d[i][j]=((j+B)*d[i-1][j]) % 998244353 + (i+A)*d[i][j-1] % 998244353 - ((i+A-1)*((j+B-1)*d[i-1][j-1]) % 998244353)% 998244353
    
print(d[C-A][D-B] % 998244353)

### FIXED CODE ###

import sys
import numpy as np
#from functools import lru_cache
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
MOD = 998_244_353
 
def main(A, B, C, D):
	d = np.zeros((C + 1, D + 1), np.int64)
	d[A,B]=1
	for i in range(A+1,C+1):
  		d[i,B] = B*d[i-1,B] % MOD
	for j in range(B+1,D+1):
		d[A,j] = A*d[A,j-1] % MOD
 
	for i in range(A+1,C+1):
		for j in range(B+1,D+1):
			d[i,j]=((((j*d[i-1,j]) % MOD + i*d[i,j-1] % MOD) % MOD) -((i-1)*((j-1)*d[i-1,j-1] % MOD)% MOD)% MOD)
    
	return d[C,D] % MOD
          
"""    
    print(d[C][D] % MOD)
    dp = np.zeros((C + 1, D + 1), np.int64)
    dp[C, D] = 1
    for d in range(D, 0, -1):
        dp[C, d - 1] = dp[C, d] * C % MOD
    for c in range(C - 1, -1, -1):
        x = 0
        for d in range(D, -1, -1):
            dp[c, d] = (d * dp[c + 1, d] + x) % MOD
            x += dp[c + 1, d]
            x *= c
            x %= MOD
    return dp[A, B]
"""

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.from_dtype(np.int64)
    signature = (i8, i8, i8, i8)
 
    cc = CC('my_module')
    cc.export('main', signature)(main)
    cc.compile()
 
from my_module import main
 
A, B, C, D = map(int, read().split())
print(main(A, B, C, D))
### BUGGY CODE ###

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

X=[]
S=[]
for _ in range(m):
    x=list(map(int,input().split()))
    X.append(x)

   
for i in range(m):
    first_num="000000"
    last_num="000000"
    
    chushutsu_list=[j for j in X if j[0]==X[i][0]]
    chushutsu_list.sort(key=lambda x:x[1])
    
    count=chushutsu_list.index(X[i])+1
    
    
    first_num=first_num[:6-len(str(X[i][0]))]+str(X[i][0])
    last_num=last_num[:6-len(str(count))]+str(count)
    print(first_num+last_num)

### FIXED CODE ###

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

X=[]

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

sort_X=sorted(X,key=lambda x:(x[1],x[2]))
sort_X[0].append(1)

for i in range(1,m):
    if sort_X[i][1]!=sort_X[i-1][1]:
        sort_X[i].append(1)
    else:
        sort_X[i].append(sort_X[i-1][3]+1)
   
X=sorted(sort_X,key=lambda x:x[0])
for i in range(m):
    count=X[i][3]
    first_num="000000"
    last_num="000000"
    
    
    first_num=first_num[:6-len(str(X[i][1]))]+str(X[i][1])
    last_num=last_num[:6-len(str(count))]+str(count)
    print(first_num+last_num)
### BUGGY CODE ###

H, W = map(int, input().split())
A = []
black = []
for i in range(H):
    A.append(list(input()))
    for j in range(W):
        if A[i][j] == '#':
            black.append([i,j])

max_dist = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            continue
        else:
            min_dist = 10000000
            for b in black:
                cur_dist = abs(b[0] - i) + abs(b[1] - j)
                if cur_dist < min_dist:
                    min_dist = cur_dist
                if min_dist == 1:
                    break
            if max_dist < min_dist:
                max_dist = min_dist

print(max_dist)

### FIXED CODE ###

H, W = map(int, input().split())
INF = H * W
A = [input() for x in range(H)]
used = [[False] * W for x in range(H)]

q = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            q.append([i, j])
            used[i][j] = True

max_dist = 0
counter = 0
depth = -1
while counter != INF:
    # print(q)
    # print(counter)
    for i in range(len(q) - counter):
        item = q[counter]

        if item[0] > 0 and not used[item[0]-1][item[1]]:
            q.append([item[0] - 1, item[1]])
            used[item[0] - 1][item[1]] = True
        if item[1] > 0 and not used[item[0]][item[1] - 1]:
            q.append([item[0], item[1] - 1])
            used[item[0]][item[1] - 1] = True
        if item[0] < H - 1 and not used[item[0] + 1][item[1]]:
            q.append([item[0] + 1, item[1]])
            used[item[0] + 1][item[1]] = True
        if item[1] < W - 1 and not used[item[0]][item[1] + 1]:
            q.append([item[0], item[1] + 1])
            used[item[0]][item[1] + 1] = True
        counter += 1
    depth += 1

print(depth)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
prebit = [0 for _ in range(20)]
prem = 0
def binl(x, accl):
    if len(accl) == 20:
        return accl
    else:
        accl.append(x%2)
        return binl(x//2, accl)
ans = 0
for i in range(1, n+1):
    m = i
    b = binl(a[i-1], [])
    for j in range(20):
        if b[j] == 1:
            m = min(m, i - prebit[j])
            prebit[j] = i
    prem = min(m, prem+1)
    ans += prem
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = cum[i] + a[i]
l = 0
r = 0
count = 0
while(r < n or l < n):
    if r < n and (cum[r] - cum[l]) & a[r] == 0:
        r += 1
    else:
        count += r - l
        l += 1
print(count)
### BUGGY CODE ###

n = int(input())
while True:
    if n%10 == n//10%10 == n // 100:
        print(n)
    else:
        n += 1

### FIXED CODE ###

n = int(input())
while True:
    if n%10 == n//10%10 == n // 100:
        print(n)
        break
    else:
        n += 1
### BUGGY CODE ###

def resolve():
    A, B, K = map(int,input().split())

    for i in range(K):
        if 1 <= A:
            A-=1
        elif 1 <= B:
            B-=1

    print("{} {}".format(A,B))

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
    A, B, K = map(int,input().split())

    '''
    for i in range(K):
        if 1 <= A:
            A-=1
        elif 1 <= B:
            B-=1
    '''

    if A < K:
        K -= A
        A = 0
        if B <= K:
            B = 0
        else:
            B -= K
    elif K <= A:
        A -= K

    print("{} {}".format(A,B))

if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

#dpで素直にやるとO(N^2)だから、累積和で高速化しO(KN)にする

n, k = map(int,input().split())
mod = 998244353

s = []
for i in range(k):
  s.append(list(map(int,input().split())))

cnt = [0]*n
cnt[0] = 1
sum = [0]*n
sum[0] = 1
for i in range(1,n):
  for j in range(k):
    if s[j][0] == s[j][1] and i >= s[j][0]:
      cnt[i] += cnt[i-s[j][0]]
    elif i > s[j][1]:
      cnt[i] += sum[i-s[j][0]] - sum[i-s[j][1]-1]
    elif i >= s[j][0]:
      cnt[i] += sum[i-s[j][0]]
    sum[i] = sum[i-1] + cnt[i]

print(cnt[-1] % mod)

### FIXED CODE ###

#dpで素直にやるとO(N^2)だから、累積和で高速化しO(KN)にする

n, k = map(int,input().split())
mod = 998244353

s = []
for i in range(k):
  s.append(list(map(int,input().split())))

cnt = [0]*n
cnt[0] = 1
sum = [0]*n
sum[0] = 1
for i in range(1,n):
  for j in range(k):
    if i > s[j][1]:
      cnt[i] += sum[i-s[j][0]] - sum[i-s[j][1]-1]
    elif i >= s[j][0]:
      cnt[i] += sum[i-s[j][0]]
    cnt[i] %= mod
    sum[i] = (sum[i-1] + cnt[i]) % mod

print(cnt[-1])
### BUGGY CODE ###

import numpy as np
n = int(input())
a = list(map(int, input().split()))
ans_lis = np.zeros(len(a))
ans_lis = np.array(ans_lis, dtype=int)
for i in range(1, len(a) + 1):
    ans_lis[i - 1] = int(a.index(i) + 1)
print(*ans_lis)

### FIXED CODE ###

n = int(input())
As = list(map(int, input().split()))
ans = [0] * n
for a, i in zip(As, range(1, n+1)):
  ans[a - 1] = i
print(*ans)
### BUGGY CODE ###

N, M = map(int, input().split())
S = str(input())
T = str(input())
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
 
X = N*M // gcd(N,M)
 
if S[0] != T[0]:
    print(-1)
elif X == N * M:
    print(X)
else:
    for i in range(1,(N*M//X)+1):
        L = X * i
        m = gcd(  L // N,  L // M)
        for j in range(1, (N*M*m//L) ):
            if S[j * L // M // m] != T[ j * L // N // m ]:
                L = -1
                break
        if L == X * i:
            break
    print(L)

### FIXED CODE ###

N, M = map(int, input().split())
S = str(input())
T = str(input())
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
 
def lcm(x, y):
    return (x * y) // gcd(x, y)
X = lcm(N ,M)
 
if S[0] != T[0]:
    print(-1)
elif X == N*M:
    print(N*M)
else:
        L = X
        match = lcm(  L // N,  L // M)
        for j in range(1, (L // match) ):
            if S[j * N * match // L] != T[ j * M * match // L]:
                L = -1
                break
        if L == X :
            print(L)
        else:
            print(-1)
### BUGGY CODE ###

import math,itertools,fractions,heapq,bisect,sys,copy,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0

  for i in range(h):
    for j in range(w):
      for k in range(h):
        for l in range(w):
          q=collections.deque()
          if field[i][j]=='#' or field[k][l]=='#':
            continue
          q.append((k,l,0))
          visited=[[-1 for __ in range(w)] for _ in range(h)]
          while len(q)>0:
            y,x,c=q.popleft()
            visited[y][x]=c
            if y==i and x==j:
              ans=max(ans,c)
              break

            for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
              ny=y+dy
              nx=x+dx
              if 0<=ny<h and 0<=nx<w:
                if field[ny][nx]=='#':
                  continue
                if visited[ny][nx]!=-1:
                  continue
                q.append((ny,nx,c+1))

  return ans

# main()
print(main())


### FIXED CODE ###

import sys,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        continue
      q.append((i,j))
      for _i in range(h):
        for _j in range(w):
          visited[_i][_j]=-1
      visited[i][j]=0
      _ans=0
      while q:
        y,x=q.popleft()

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if not 0<=ny<h:
            continue
          if not 0<=nx<w:
            continue
          if field[ny][nx]=='#':
            continue
          if visited[ny][nx]!=-1:
            continue
          _ans=visited[y][x]+1
          visited[ny][nx]=_ans
          q.append((ny,nx))
      ans=max(ans,_ans)
  return ans

# main()
print(main())
### BUGGY CODE ###

count = 0
def count_buttle(h):
    global count
    if h == 1:
        count += 1
        return
    h = h//2
    count += 1
    count_buttle(h)
    count_buttle(h)
H = int(input())
count_buttle(H)
print(count)

### FIXED CODE ###

import math
H = int(input())
count = int((1-2**(math.floor(math.log2(H))+1)) * -1)
print(count)
### BUGGY CODE ###

A, B, C, D=map(int, input().split())
cnt=0

for i in range(A, B+1):
  if i%C !=0 and i%D !=0:
    cnt +=1
print(cnt)

### FIXED CODE ###

import fractions
a, b, c, d=map(int, input().split())
k=fractions.gcd(c, d)
lcm=c*d//k
x=b//c - (a-1)//c
y=b//d - (a-1)//d
z=b//lcm - (a-1)//lcm
print(b-a+1-(x+y-z))
### BUGGY CODE ###

#!/usr/bin/env python3

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

N_1 = abs(N - K)

while N_1 <= N:
    N = N_1
    N_1 = abs(N_1 - K)

print(N)

### FIXED CODE ###

#!/usr/bin/env python3

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

t_1 = N % K
t_2 = K - t_1

if t_1 > t_2:
    print(t_2)
else:
    print(t_1)
### BUGGY CODE ###

# import bisect
# from collections import Counter, deque # https://note.nkmk.me/python-scipy-connected-components/
# from copy import copy, deepcopy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    S = list(input())
    ls = len(S)

    rr = [0] * (ls + 1)
    ll = [0] * (ls + 1)

    for i in range(ls):
        j = 0
        r = 0
        while True:
            if i + j < ls:
                if S[i + j] == '>':
                    r += 1
                    j += 1
                else:
                    rr[i] = r
                    break
            else:
                rr[i] = r
                break

    for i in range(1,ls+1):
        j = 0
        l = 0
        while True:
            if i - j-1 >= 0:
                if S[i - j-1] == '<':
                    l += 1
                    j += 1
                else:
                    ll[i] = l
                    break

            else:
                ll[i] = l
                break

    ans = 0
    for i in range(ls + 1):
        ans += max(ll[i], rr[i])
    print(ans)


resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()


def resolve():
    S = list(input())
    ls = len(S)

    rr = [0] * (ls + 1)
    ll = [0] * (ls + 1)

    for i in range(ls):
        if S[i] == '<':
            ll[i+1]=ll[i]+1
    for i in reversed(range(ls)):
        if S[i] == '>':
            rr[i]=rr[i+1]+1


    ans = 0
    for i in range(ls + 1):
        ans += max(ll[i], rr[i])
    print(ans)


resolve()
### BUGGY CODE ###


n = int(input())
a = list(map(int,input().split()))
ans = 0
b = []

for i in range(n):
    for j in range(i+1,n+1):
        b = a[i:j]
#        print(b)

        if sum(b) == 0:
            ans += 1

print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[0]
for i in range(n):
  b.append(b[-1]+a[i])
#print(b)
ans = 0
b.sort()
for i in range(n+1):
  if i == 0:
    x=b[0]
    m=1
  else:
    if x==b[i]:
      m+=1
      if i==n:
        ans += m*(m-1)//2
    else:
      if m!=1:
        ans += m*(m-1)//2
        m=1
      x=b[i]
print(ans)
### BUGGY CODE ###

H,N = map(int,input().split())
spells = sorted([tuple(map(int,input().split())) for _ in range(N)], key=lambda c: c[0])
max_a = spells[-1][0]

dp = [100000000 for _ in range(H + max_a + 1)]
dp[0] = 0

for i in range(1, H + max_a + 1):
  for spell in spells:
    if spell[0] <= i:
      dp[i] = min(dp[i], dp[i - spell[0]] + spell[1])
    else:
      break

print(min(dp[H:H + max_a + 1]))


### FIXED CODE ###

H,N = map(int,input().split())
spells = [tuple(map(int,input().split())) for _ in range(N)]
max_a = max(spells)[0]

dp = [0]
for i in range(1, H + max_a + 1):
  try:
    dp.append(min([dp[i - a] + b for a,b in spells if a <= i]))
  except ValueError:
    dp.append(10**8)

print(min(dp[H:]))
### BUGGY CODE ###

N,P=map(int,input().split())
S=input()
if P==2 or P==5:
    x=0
    for j in range(len(S)):
        if int(S[j])%P==0:
            x+=j+1
    print(x)
else:
    A=[0]*P
    a=0
    b=1
    for i in range(len(S)):
        a=(a+int(S[(len(S)-1-i)])*(b%P))%P
        A[a]+=1
        b=b*10
    x=A[0]
    for k in range(P):
        x+=int(A[k]*(A[k]-1)/2)
    print(x)

### FIXED CODE ###

N,P=map(int,input().split())
S=input()
if P==2 or P==5:
    x=0
    for j in range(N):
        if int(S[j])%P==0:
            x+=j+1
    print(x)
else:
    A=[0]*P
    a=0
    b=1
    for i in range(N):
        a=(a+int(S[(N-1-i)])*b)%P
        A[a]+=1
        b=(b*10)%P
    x=A[0]
    for k in range(P):
        x+=int(A[k]*(A[k]-1)/2)
    print(x)
### BUGGY CODE ###

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

i=1
while i<=a:
  print(li.count(i))
  i+=1

### FIXED CODE ###

from collections import Counter

n = int(input())
li = input().split()
a = Counter(li)


for i in range(1,n+1):
  print(a[str(i)])
### BUGGY CODE ###

def swap(A, i, j):
    tmp = A[i]
    A[i] = A[j]
    A[j] = tmp


def count_inversion(A):
    cnt = 0
    for i in range(len(A)):
        for j in reversed(range(i + 1, len(A))):
            if A[j] < A[j - 1]:
                swap(A, j, j - 1)
                cnt += 1
    # print(A)
    return cnt


def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    print(count_inversion(A))


main()


### FIXED CODE ###

#! /usr/local/bin/python3
# coding: utf-8

from math import inf

inv = 0


def merge(A, left, mid, right):
    global inv

    L = A[left:mid]
    L.append(inf)
    R = A[mid:right]
    R.append(inf)
    i = j = 0
    for k in range(left, right):
        if L[i] < R[j]:
            A[k] = L[i]
            i += 1
        else:
            inv += len(L) - i - 1
            A[k] = R[j]
            j += 1


def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)


def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    merge_sort(A, 0, n)
    print(inv)


main()
### BUGGY CODE ###

#16D8101012J 伊藤惇 dj Python3

def Maximum_Profit(n,A):
    Max=(min(A)-max(A))
    for i in range(n-1):
        tmp=(max(A[i+1:])-A[i])
        if Max<tmp:
            Max=tmp
    return Max

if __name__ == "__main__":
    n=int(input())
    A=[]
    for i in range(n):
        A.append(int(input()))
    Max=Maximum_Profit(n,A)
    print(Max)



### FIXED CODE ###

#16D8101012J 伊藤惇 dj Python3

def Maximum_Profit(n,A):
    Max=A[1]-A[0]
    Min=A[0]
    for j in range(1,n):
        Max=max(Max,A[j]-Min)
        Min=min(Min,A[j])
    return Max

if __name__ == "__main__":
    n=int(input())
    A=[]
    for i in range(n):
        A.append(int(input()))
    Max=Maximum_Profit(n,A)
    print(Max)
### BUGGY CODE ###

n,m=(int(i) for i in input().split())
a,b=(int(i) for i in input().split())
myset=set()
for i in range(a,b+1):
    myset.add(i)
if m==1:
  ans=myset
else:
  ans=myset
  for i in range(1,m):
    a,b=(int(i) for i in input().split())
    myset=set()
    for i in range(a,b+1):
      myset.add(i)
    ans=ans&myset

print(len(ans))

### FIXED CODE ###

n,m=(int(i) for i in input().split())
list_a=[]
list_b=[]
for i in range(m):
  a,b=(int(i) for i in input().split())
  list_a.append(a)
  list_b.append(b)
  
max_a=max(list_a)
min_b=min(list_b)

if min_b-max_a+1>=0:
  print(min_b-max_a+1)
else:
  print(0)
### BUGGY CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
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 main():
    md=10**9+7
    n, m = MI()
    rtol = defaultdict(list)
    for _ in range(m):
        l, r, x = MI()
        rtol[r].append([l, x])
    dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    dp[0][0][0] = 1
    ans = 0
    for r in range(n):
        for g in range(n):
            for b in range(n):
                pre = dp[r][g][b]
                if pre == 0: continue
                i = max(r, g, b) + 1
                dp[i][g][b] += pre
                dp[r][i][b] += pre
                dp[r][g][i] += pre
                for l, x in rtol[i]:
                    over_l = [r >= l, g >= l, b >= l]
                    if over_l[1] + over_l[2] + 1 != x:
                        dp[i][g][b] = 0
                    if over_l[0] + over_l[2] + 1 != x:
                        dp[r][i][b] = 0
                    if over_l[0] + over_l[1] + 1 != x:
                        dp[r][g][i] = 0
                #if i == n:
                #    ans += dp[i][g][b] + dp[r][i][b] + dp[r][g][i]
    ans+=sum(dp[i][j][n] for i in range(n) for j in range(n))
    ans%=md
    ans+=sum(dp[i][n][j] for i in range(n) for j in range(n))
    ans%=md
    ans+=sum(dp[n][j][i] for i in range(n) for j in range(n))
    ans%=md
    print(ans)

main()


### FIXED CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
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)]

# 一番後ろの色を(赤に)固定した上で、もらうDPに書き換え
def main():
    md = 10 ** 9 + 7
    n, m = MI()
    rtol = defaultdict(list)
    for _ in range(m):
        l, r, x = MI()
        rtol[r].append([l, x])
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for k in range(1, n + 1):
        for i in range(k - 1):
            dp[i][k - 1] = dp[k - 1][i] = sum(dp[i][:k - 1]) % md
        for l, x in rtol[k]:
            if x == 1:
                for i in range(l, k):
                    for j in range(k):
                        dp[i][j] = dp[j][i] = 0
            if x == 2:
                for i in range(l, k):
                    for j in range(i + 1, k):
                        dp[i][j] = dp[j][i] = 0
                for i in range(l):
                    for j in range(i + 1):
                        dp[i][j] = dp[j][i] = 0
            if x == 3:
                for i in range(l):
                    for j in range(k):
                        dp[i][j] = dp[j][i] = 0

    # p2D(dp)
    print(sum(sum(dr) for dr in dp) * 3 % md)

main()
### BUGGY CODE ###

N, K = [int(_) for _ in input().split()]
for a in range(10**9):
    if K**(a) <= N < K**(a*1):
        print(a+1)
        break

### FIXED CODE ###

N, K = [int(_) for _ in input().split()]
for a in range(0, 10**9):
    if K**(a) <= N < K**(a+1):
        print(a+1)
        break
### BUGGY CODE ###

n = int(input())
k = 1
x = []
y = []
for i in range(1, n+1):
  if n % (k*i) == 0:
    x.append(k*i)
    y.append(n//(k*i))
    if n // (k*i) < k*i:
      break

print(x[len(x)-2] + y[len(x)-2] -2)

### FIXED CODE ###

import math
n = int(input())
x = []
m = int(math.sqrt(n))
for i in range(1, m+1):
  if n % i == 0:
    x.append(n//i + i -2)
print(min(x))
### BUGGY CODE ###


s=input()
n=len(s)
t=input()
m=len(t)
dp=[["" for i in range(m)] for j in range(n)]

for i in range(n):
	for j in range(m):
		if s[i]==t[j]:
			if j==0 or i==0:
				x=""
			else:
				x=dp[i-1][j-1]
			dp[i][j]=x+s[i]
		else:
			if i==0:
				a=""
			else:
				a=dp[i-1][j]
			if j==0:
				b=""
			else:
				b=dp[i][j-1]
			if len(a)>len(b):
				dp[i][j]=a
			else:
				dp[i][j]=b
print(dp[n-1][m-1])

### FIXED CODE ###

s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1,n+1):
	for j in range(1,m+1):
		if s[i-1]==t[j-1]:
			dp[i][j]=dp[i-1][j-1]+1
		else:
			dp[i][j]=max(dp[i-1][j],dp[i][j-1])
i=n
j=m
st=""
while dp[i][j]:
	while dp[i-1][j]==dp[i][j]:
		i-=1
	while dp[i][j-1]==dp[i][j]:
		j=j-1
	j-=1
	st+=s[i-1]
	i-=1
print(st[::-1])
### BUGGY CODE ###

N = int(input())
for i in range(1,10000000000):
  if i % 2 == 0 and i % N == 0:
    print(i)
    break

### FIXED CODE ###

N = int(input())
if N % 2 == 0:
  print(N)
else:
  print(N*2)