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

import sys
import collections

def main():
    N,*S = map(int, open(0).read().split())

    S = sorted(S)

    g = [S.pop(-1)]

    for _ in range(N):
        parents = g[:]
        for p in parents:
            for si, s in enumerate(S[::-1]):
                if p > s:
                    g.append(s)
                    del S[-(si+1)]
                    break
            else:
                print('No')
                sys.exit()
    print('Yes')

if __name__=='__main__':
    main()

### FIXED CODE ###

## 他の方と処理内容がほぼ同じなのに何でTLEになるか分からないので、他の方のコードでテスト
N = int(input())
a = list(map(int,input().split(' ')))
a.sort()
    

fathers = [a.pop()]
for _ in range(N):
    sons = list()
    b = list()
    
    for father in fathers:
        while a:
            x = a.pop()
            if father > x:
                sons.append(x)
                break
            else:
                b.append(x)
                
    a = a + b[::-1]
    fathers.extend(sons)
    fathers.sort(reverse = True)
    
    
    
if len(fathers) == 2**N:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

n,m,k=map(int,input().split())
mod=998244353
if m==1:print(0 if k!=n-1 else 1);exit()

fact=[1]*(n-1+1)
inv=[1]*(n-1+1)
for i in range(2,n-1+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(n-1,1,-1):
    inv[i-1]=inv[i]*i%mod
ans=0
po=pow(m-1,n-1,mod)
ue=fact[n-1]
iii=pow(m-1,mod-2,mod)
for i in range(k+1):
    ans+=ue*inv[n-1-i]*inv[i]%mod*m*po%mod
    po*=iii
    ans%=mod
print(ans)

### FIXED CODE ###

n,m,k=map(int,input().split())
mod=998244353
if m==1:print(0 if k!=n-1 else 1);exit()
fact=[1]*(n-1+1)
inv=[1]*(n-1+1)
for i in range(2,n-1+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(n-1,1,-1):
    inv[i-1]=inv[i]*i%mod
ans=0
po=pow(m-1,n-1,mod)*m%mod
ue=fact[n-1]
iii=pow(m-1,mod-2,mod)%mod
for i in range(k+1):
    ans+=ue*inv[n-1-i]%mod*inv[i]%mod*po%mod
    po*=iii
    po%=mod
print(ans%mod)
### BUGGY CODE ###

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

counter = 0
for x in range(K + 1):
  for y in range(K + 1):
    for z in range(K + 1):
      total = x + y + z
      if total == S:
        counter += 1

print(counter)

### FIXED CODE ###

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

counter = 0
for x in range(K + 1):
  for y in range(K + 1):
    z = S - (x + y)
    if z >= 0 and z <= K:
      counter += 1

print(counter)
### BUGGY CODE ###

from collections import Counter

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

for i in range(n):
    new_list = []
    Sum = 0
    if i == 0:
        new_list = li[1:n]
        S=Counter(new_list)
        for k in range(n):
            if S[k] > 1:
                Sum += (S[k] * (S[k] -1)) / 2
            else:
                continue
        print(int(Sum))
    elif i == n-1:
        new_list = li[:n-1]
        S=Counter(new_list)
        for k in range(n):
            if S[k] > 1:
                Sum += (S[k] * (S[k] -1)) / 2
            else:
                continue
        print(int(Sum))
    else:
        new_list = li[:i] + li[i+1:]
        S=Counter(new_list)
        for k in range(n):
            if S[k] > 1:
                Sum += (S[k] * (S[k] -1)) / 2
            else:
                continue
        print(int(Sum))

### FIXED CODE ###

from collections import Counter
import sys
input = sys.stdin.readline
n = int(input())
li = list(map(int,input().split()))
S=Counter(li)
Sum = 0
for k in range(n):
            if S[k+1] > 1:
                Sum += (S[k+1] * (S[k+1] -1)) / 2
            else:
                continue

#k個目が何なのかを考える
for i in range(n):
    if S[li[i]] > 1:
        Sum_2 = Sum
        Sum_2 = Sum_2 - (S[li[i]] * (S[li[i]] -1)) / 2 + ((S[li[i]]-1) * (S[li[i]] -2)) / 2
        print(int(Sum_2))
    else:
        print(int(Sum))
### BUGGY CODE ###

from collections import deque
h,w = list(map(int,input().split()))
s = [[x for x in input()] for _ in range(h)]

def find_w():
  for i in range(h):
    for j in range(w):
      if s[i][j] == '.':
        return True

def find_b():
  b = deque([])
  for i in range(h):
    for j in range(w):
      if s[i][j] == '#':
        b.append([i,j])
  return b

d = [[float('inf') for _ in range(w)] for _ in range(h)]
def bfs():
  que = deque([])
  que.extend(find_b())
  dh = [1,0,-1,0]
  dw = [0,1,0,-1]
  while que:
    p = que.pop()
    for i in range(4):
      nh = p[0] + dh[i]
      nw = p[1] + dw[i]
      
      if nh >= 0 and nh < h and nw >= 0 and nw < w and \
          s[nh][nw] == '.' and d[nh][nw] == float('inf'):
        s[nh][nw] = '#'

cnt = 0
while find_w():
  bfs()
  cnt += 1

print(cnt)


### FIXED CODE ###

from collections import deque

h,w = list(map(int,input().split()))
m = [[x for x in input()] for _ in range(h)]
next_que = deque([])
for i in range(h):
  for j in range(w):
    if m[i][j] == '#':
      next_que.append([i,j])


dh = [1,0,-1,0]
dw = [0,1,0,-1]

def bfs(next_que):
  cnt = -1
  while next_que:
    cnt += 1
    que = list(next_que)
    next_que = deque([])
    for cur in que:
      #cur = que.popleft()
      for i in range(4):
        nh = cur[0] + dh[i]
        nw = cur[1] + dw[i]
        
        if nh >= 0 and nh < h and nw >= 0 and nw < w and m[nh][nw] == '.':
          m[nh][nw] = '#'
          next_que.append([nh,nw])
  
  return cnt



cnt = bfs(next_que) 

print(cnt)
### BUGGY CODE ###

import sys

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

inf = float('inf')
for i in range(N):
	E[i][i] = inf

for k in range(N):
	for i in range(N):
		if i == k:
			continue
		for j in range(N):
			if k == j or i == j:
				continue
			direct = E[i][j]
			detour = E[i][k]+E[k][j]
			if direct == inf or detour == inf:
				continue

			if direct > detour:
				print(-1)
				sys.exit()

			elif direct == detour:		
				E[i][j] = inf
				E[j][i] = inf

answer = 0
for i in range(N):
	for j in range(N):
		if E[i][j] == inf:
			continue
		
		answer += E[i][j]

print(answer//2)

### FIXED CODE ###

import sys

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

inf = float('inf')
for i in range(N):
	E[i][i] = inf

for k in range(N):
	for i in range(N):
		if i == k:
			continue
		for j in range(N):
			if k == j or i == j:
				continue
			direct = E[i][j]
			detour = E[i][k]+E[k][j]
			if direct == inf or detour == inf:
				continue

			if direct > detour:
				print(-1)
				sys.exit()

			elif direct == detour:		
				E[i][j] = inf
				E[j][i] = inf

answer = 0
for i in range(N):
	for j in range(N):
		if E[i][j] == inf:
			continue
		
		answer += E[i][j]

print(answer//2)
### BUGGY CODE ###

#-*-coding:utf-8-*-

def main():
    n, m = map(int, input().split())
    ans = 1
    for i in range(1, int(m**0.9)+10):
        if m % i == 0 and m // i >= n:
            ans = max(ans, i)
    print(ans)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

#-*-coding:utf-8-*-

def main():
    n, m = map(int, input().split())
    ans = 1
    for i in range(1, int(m**0.5)+1):
        if m % i == 0:
            if m >= i * n:
                ans = max(ans, i)
            if m >= (m // i) * n:
                ans = max(ans, m // i)
    print(ans)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    jobs = {}
    for _ in range(N):
        A, B = map(int, input().split())
        if A in jobs.keys():
            jobs[A] = jobs[A] + [B]
        else:
            jobs[A] = [B]

    profit = 0
    potential_jobs = []

    # M-1日後から今日まで遡る
    for elappsed_day in range(1, M+1):
        if elappsed_day in jobs.keys():
            potential_jobs += jobs[elappsed_day]
        if len(potential_jobs) > 0:
            profit += max(potential_jobs)
            potential_jobs.remove(max(potential_jobs))
            
    print(profit)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from heapq import heappush, heappop
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    jobs = {}
    for _ in range(N):
        A, B = map(int, input().split())
        if A > M:
            continue
        if A in jobs.keys():
            jobs[A] += [-B]
        else:
            jobs[A] = [-B]

    profit = 0
    days = jobs.keys()
    potential_jobs = []
    
    # M-1日後から今日まで遡る
    for elappsed_day in range(1, M+1):
        if elappsed_day in days:
            for job in jobs[elappsed_day]:
                heappush(potential_jobs, job)
        if len(potential_jobs) > 0:
            profit += heappop(potential_jobs)
            
    print(-profit)

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

n,k = map(int,input().split())
p = list(map(int,input().split()))

c=0

x=0

for i in range(1,n-k+1):
#  print(sum(p[x:x+k]),sum(p[i:i+k]))
  if sum(p[x:x+k])<sum(p[i:i+k]):
    x=i
#print(x)
for i in range(x,x+k):
  z=0
  for j in range(0,p[i]+1):
    z+=j
#  print(z)
#  print(p[i])
  c+=z/p[i]
print(c)

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))

c=0
x=0
m=sum(p[0:k])
z=m
for i in range(1,n-k+1):
#  print(z,p[i-1],p[i+k-1])
  z=z-p[i-1]+p[i+k-1]
#  print(m,z)
  if m<z:
    m=z
    x=i
#print(x)
for i in range(x,x+k):
#  print(p[i])
  c+=((p[i]*(p[i]+1))/2)/p[i]
print(c)
### BUGGY CODE ###

import sys
import numpy as np

def main(inp):
    N,M=map(int,next(inp).split())
    X=np.array(list(map(int,next(inp).split())))
    X=np.sort(X)
    
    if(N>M): return 0
    if(N==1):
        ans=X[len(X)-1]-X[0]
        return ans
    
#     print(N,M,X)
    
    delta=np.empty([M-1],dtype=int)
    
    for i in range(M-1):
        delta[i]=X[i+1]-X[i]
    
#     print(X)
#     print(delta)
    
    
    #delta=np.split(delta,[1,2])
    #print(delta)
    
    splpoint=np.argpartition(np.array(delta),-N+1)[-N+1:]
    splpoint=np.sort(splpoint)
    for i in range(len(splpoint)):
        splpoint[i]+=1
    
#     delta=np.delete(delta,splpoint)
#     print(delta)    
#     print(splpoint)
    
    spl=np.split(X,splpoint)
#     print(spl)
    
    ans=0
    for i in range(len(spl)):
        ans+=spl[i][len(spl[i])-1]-spl[i][0]
        
    return ans
  
print(main(sys.stdin))


### FIXED CODE ###

import sys
import numpy as np

def main(inp):
    N,M=map(int,next(inp).split())
    X=np.array(list(map(int,next(inp).split())))
    X=np.sort(X)
        
#     N=inp[0]
#     M=inp[1]    
#     X=np.array(inp[2])
    X=np.sort(X)    
#    print("N",N)
#    print("M",M)
#    print("X",X)
    
    if(N>M): return 0
    if(N==1):
        ans=X[len(X)-1]-X[0]
        return ans
    
    delta=np.empty([M-1],dtype=int)
    
    for i in range(M-1):
        delta[i]=X[i+1]-X[i]
    
#    print(X)
#    print("delta",delta)
    
    
    #delta=np.split(delta,[1,2])
    #print(delta)
    
    splpoint=np.argpartition(np.array(delta),-N+1)[-N+1:]
#     splpoint=np.sort(splpoint)
    
    delta=np.delete(delta,splpoint)
#    print(splpoint)
#    print(delta)    
    
    ans=sum(delta)
        
    return ans

print(main(sys.stdin))
### BUGGY CODE ###

l,r=map(int,input().split())
if r>l+4040:
    r=l+4040
minimum=1000000000
for i in range(l,r+1):
    for j in range(i+1,r+1):
        minimum=min(minimum,((i*j)%2019))
print(minimum)

### FIXED CODE ###

l,r=map(int,input().split())
if r>l+4040:
    r=l+4040
dif=r-l
minimum=1000000000
for i in range(l%2019,l%2019 + dif+1):
    for j in range(i+1,l%2019 +dif +1):
        minimum=min(minimum,((i*j)%2019))
print(minimum)
### BUGGY CODE ###

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

A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse = True)

def calc(x): #全てx以下にするために何回変える必要があるか
    tmp = 0
    for a, f in zip(A, F):
        tmp += max(0, a - (x // f))
    return tmp

ng = -1
ok = 10 ** 18
while ok - ng > 1:
    mid = (ok + ng) // 2
    if calc(mid) <= K:
        ok = mid
    else:
        ng = mid

print (ok)

### FIXED CODE ###

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

A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse = True)

def calc(x): #全てx以下にするために何回変える必要があるか
    tmp = 0
    for a, f in zip(A, F):
        tmp += max(0, a - (x // f))
    return tmp

ng = -1
ok = 10 ** 18
while ok - ng > 1:
    mid = (ok + ng) // 2
    if calc(mid) <= K:
        ok = mid
    else:
        ng = mid

print (ok)
### BUGGY CODE ###

import re

S = str(input())
k=int(0)

#for i in range(2000):
#while () :
a = int(1)
while a!=0:
#    S = S[:S.rfind('ABC')] + 'BCA' + S[(S.rfind('ABC')+3):]
#    k +=1
    a = len(re.findall("ABC",S))
    k += a
    S = S.replace('ABC', 'BCA')
#    if a==0 : break

print(int(k))

### FIXED CODE ###

s = input()
ans = 0
cntA = 0
for i in range(0, len(s) - 1):
    if s[i] == 'A':
        cntA += 1
    elif s[i: i + 2] == "BC":
        ans += cntA
    elif i > 0 and s[i - 1: i + 1] == "BC":
        continue
    else:
        cntA = 0
print(ans)
### BUGGY CODE ###

##解説参照
##b,b-aを判定に使うことが困難
n=int(input())
p=[];m=[]
for _ in range(n):
    s=input()
    cnt=0;a=0;b=0
    for i in range(len(s)):
        if s[i]==")":
            cnt+=1
        else:
            cnt-=1
        a=max(a,cnt)
    cnt=0
    for i in range(len(s)-1,-1,-1):
        if s[i]=="(":
            cnt+=1
        else:
            cnt-=1
        b=max(b,cnt)
    if b-a>=0:
        p.append((a,s))
    else:
        m.append((-b,s))
p.sort();m.sort()
ss=""

for _,s in p:
    ss+=s
for _,s in m:
    ss+=s
cnt=0
for i in range(len(ss)):
    if ss[i]=="(":
        cnt+=1
    else:
        cnt-=1
    if cnt<0:
        print("No")
        exit()
if cnt:
    print("No")
else:
    print("Yes")



### FIXED CODE ###

import sys
input = sys.stdin.readline

n=int(input())
s=[input().strip("\n") for _ in range(n)]
p=[];m=[]
for si in s:
    cnt=0;a=0;b=0
    for i in range(len(si)):
        if si[i]==")":
            cnt+=1
        else:
            cnt-=1
        a=max(a,cnt)
    cnt=0
    for i in range(len(si)-1,-1,-1):
        if si[i]=="(":
            cnt+=1
        else:
            cnt-=1
        b=max(b,cnt)
    if b-a>=0:
        p.append((a,si))
    else:
        m.append((-b,si))
p.sort();m.sort()
ss=""

for _,si in p:
    ss+=si
for _,si in m:
    ss+=si
cnt=0
for i in range(len(ss)):
    if ss[i]=="(":
        cnt+=1
    else:
        cnt-=1
    if cnt<0:
        print("No")
        exit()
if cnt:
    print("No")
else:
    print("Yes")
### BUGGY CODE ###

import queue
def main():
    n,m=map(int,input().split())
    root=[[0 for i in range(n)] for i in range(n)]
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1][b-1]=1
        root[b-1][a-1]=1
    min=[-1 for i in range(n)]
    min[0]=2
    dict={}
    for i in range(n):
        dict[i]=-1

    start=0
    check=[False]*n
    toVis=queue.Queue()
    check[start]=True
    for i in range(len(root[0])):
        if root[0][i]==1:
            toVis.put(i)
            dict[i]=start
        #   print(i,":",start)
            check[i]=True
    while(toVis.empty()!=True):
        now=toVis.get()
        #print(now)
        check[now]=True
        for i in range(n):
            if root[now][i]==1 and check[i]==False:
                toVis.put(i)
                dict[i]=now
            # print(i,":",now)
                check[i]=True
    #print(dict)  
    for i in range(1,n):
        if dict[i]==-1:
            print("No")
            return 0
    print("Yes")
    for i in range(1,n):
        print(dict[i]+1)         


if __name__=="__main__":
    main()

### FIXED CODE ###

from collections import deque
def main():
    n,m=map(int,input().split())
    root=[[] for i in range(n)]
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
    dict={}
    for i in range(n):
        dict[i]=-1

    start=0
    check=[False]*n
    toVis=deque()
    check[start]=True
    for v in root[start]:
        toVis.append(v)
        dict[v]=start
    #   print(i,":",start)
        check[v]=True
    while len(toVis)>0:
        now=toVis.popleft()
        #print(now)
        check[now]=True
        for v in root[now]:
            if check[v]==False:
                toVis.append(v)
                dict[v]=now
            # print(i,":",now)
                check[v]=True
    #print(dict)  
    for i in range(1,n):
        if dict[i]==-1:
            print("No")
            return 0
    print("Yes")
    for i in range(1,n):
        print(dict[i]+1)         


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

A, B, Q = map(int, input().split())
S = [int(input()) for _ in range(A)]
T = [int(input()) for _ in range(B)]
X = [int(input()) for _ in range(Q)]
INF = 10**12

def binary_search(query, arr):
    arr = [-INF] + arr + [INF]
    low = 0
    high = len(arr)
    t = (low+high)//2
    while low<high-1:
        if query>arr[t]:
            low = t
        else:
            high = t
        t = (low+high)//2
    return arr[low], arr[high]

def main():
    for x in X:
        s1, s2 = binary_search(x, S)
        t1, t2 = binary_search(x, T)
        ans = INF
        for s in [s1, s2]:
            for t in [t1, t2]:
                d1 = abs(t-x) + abs(s-t)
                d2 = abs(s-x) + abs(t-s)
                ans = min(ans, d1, d2)
        print(ans)
    return

main()

### FIXED CODE ###

A, B, Q = map(int, input().split())
INF = 10**12
S = [-INF] + [int(input()) for _ in range(A)] + [INF]
T = [-INF] + [int(input()) for _ in range(B)] + [INF]
X = [int(input()) for _ in range(Q)]


def binary_search(query, arr):
    low = 0
    high = len(arr)
    while high-low>1:
        mid = (low+high)//2
        if query>arr[mid]:
            low = mid
        else:
            high = mid
    return arr[low], arr[high]

def main():
    for x in X:
        s1, s2 = binary_search(x, S)
        t1, t2 = binary_search(x, T)
        ans = [ abs(t-s)+min(abs(t-x), abs(s-x)) \
            for t in [t1, t2] for s in [s1, s2] ]
        print(min(ans))
    return

main()
### BUGGY CODE ###

import itertools
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

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

X = XY[:, 0]
Y = XY[:, 1]
X = X[Y.argsort()]
Y = Y[Y.argsort()]

ans = INF
for xi, xj in itertools.combinations(range(N), r=2):
    L, r = min(X[xi], X[xj]), max(X[xi], X[xj])
    xconds = (L <= X) & (X <= r)

    yi = 0
    yj = 1
    while yj < N:
        b, u = min(Y[yi], Y[yj]), max(Y[yi], Y[yj])
        count = np.sum(xconds & (b <= Y) & (Y <= u))
        if count >= K:
            ans = min(ans, (r - L) * (u - b))
            yi += 1
        else:
            yj += 1
        if yi == yj:
            yj += 1
print(ans)


### FIXED CODE ###

import itertools
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

N, K = list(map(int, next(sys.stdin).split()))
XY = np.array([list(map(int, next(sys.stdin).split())) for _ in range(N)])

X = XY[:, 0]
Y = XY[:, 1]
X = X[Y.argsort()]
Y = Y[Y.argsort()]

ans = INF
for xi, xj in itertools.combinations(range(N), r=2):
    L, r = min(X[xi], X[xj]), max(X[xi], X[xj])
    xconds = (L <= X) & (X <= r)

    yi = 0
    yj = 1
    while yj < N:
        if np.sum(xconds[yi:yj + 1]) >= K:
            b, u = min(Y[yi], Y[yj]), max(Y[yi], Y[yj])
            ans = min(ans, (r - L) * (u - b))
            yi += 1
        else:
            yj += 1
        if yi == yj:
            yj += 1
print(ans)
### BUGGY CODE ###

import bisect
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort()
B.sort()
C.sort()
ans=0
for a in range(N):
    for b in range(bisect.bisect_right(B,A[a]),N):
        for c in range(bisect.bisect_right(C,B[b]),N):
            
            if A[a]<B[b]<C[c]:
                ans+=1
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort()
B.sort()
C.sort()
ans=0
for b in range(N):
    a=bisect.bisect_left(A,B[b])
    c=N-bisect.bisect_right(C,B[b])
    ans+=a*c
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
class sieve:
  def __init__(self, n):
    self.n = n
    self.sv = [1] * (n + 1)
    self.sv[0] = 0
    self.sv[1] = 0
    for i in range(2, n + 1):
      if self.sv[i]:
        for j in range(i * 2, n + 1, i):
          self.sv[j] = 0
  def isprime(self, x):
    if x > self.n:
      return False
    return self.sv[x] == 1
  def factorize(self, x):
    res = []
    for i in range(2, self.n + 1):
      if self.sv[i]:
        while x % i == 0:
          x //= i
          res.append(i)
    if x != 1:
      res.append(x)
    return res
  def modgcd(self, a, mod):
    res = [float("inf")] * (self.n + 1)
    vis = set()
    f = self.factorize(a[0])
    for j in f:
      res[j] = f.count(j)
      vis.add(j)
    for i in range(1, len(a)):
      f = self.factorize(a[i])
      for j in vis:
        res[j] = min(f.count(j), res[j])
        vis.add(j)
    rres = 1
    for i in range(self.n + 1):
      if res[i] != float("inf"):
        rres *= pow(i, res[i], mod)
        rres %= mod
    return rres
  def modlcm(self, a, mod):
    res = [0] * (self.n + 1)
    for i in range(len(a)):
      f = self.factorize(a[i])
      for j in f:
        res[j] = max(f.count(j), res[j])
    rres = 1
    for i in range(self.n + 1):
      if res[i] != 0:
        rres *= pow(i, res[i], mod)
        rres %= mod
    return rres
sv = sieve(10 ** 6)
lcm = sv.modlcm(a, 10 ** 9 + 7)
res = 0
for x in a:
  res += lcm * pow(x, 10 ** 9 + 5, 10 ** 9 + 7)
res %= 10 ** 9 + 7
print(res)

### FIXED CODE ###

import sys
from fractions import gcd
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
l = 1
res = 0
for x in a:
  l = x * l // gcd(x, l)
l %= mod
for x in a:
  res += l * pow(x, mod - 2, mod)
  res %= mod
print(res)
### BUGGY CODE ###

n,k = map(int,input().split())
ns = []
for i in range(k):
    l, r = map(int,input().split())
    for k in range(l, r+1):
        ns.append(k)
arr = [0 for i in range(n)]
arr[0] = 1
for i in range(n):
    for j in ns:
        if i + j < n:
            arr[i + j] += arr[i]
print(arr[n-1] % 998244353)

### FIXED CODE ###

MOD = 998244353
n,k = map(int,input().split())
ns = [list(map(int,input().split())) for i in range(k)]
    
dp = [0 for j in range(n+1)]
cum = [0 for j in range(n+1)]
dp[1] = 1
cum[1] = 1
for i in range(2, n+1):
    for j in range(k):
        l, r = ns[j]
        if i - l >= 0:
            dp[i] += cum[i-l]
        if i - (r+1) >= 0:
            dp[i] -= cum[i-(r+1)]
    dp[i] = (dp[i] % MOD + MOD) % MOD
    cum[i] = (cum[i-1] + dp[i]) % MOD
print(dp[n])