Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
k_list=[]

for i in range(k):
    l,r=map(int,input().split())
    k_list.append([l,r])

dp=[0]*(n+1)
dp[1]=1
dpsum=[0]*(n+1)
dpsum[1]=1

for i in range(1,n):
    dpsum[i]=dp[i]+dpsum[i-1]
    for j in range(k):
        l,r=k_list[j]
        li=i+l
        ri=i+r+1
        if li<=n:
            dp[li]+=dpsum[i]
        if ri<=n:
            dp[ri]-=dpsum[i]

print(dp[n]%998244353)


Fixed submission:
n,k=map(int,input().split())
k_list=[]

for i in range(k):
    l,r=map(int,input().split())
    k_list.append([l,r])

dp=[0]*(n+1)
dp[1]=1
dpsum=[0]*(n+1)
dpsum[1]=1

for i in range(1,n):
    dpsum[i]=dp[i]+dpsum[i-1]
    for j in range(k):
        l,r=k_list[j]
        li=i+l
        ri=i+r+1
        if li<=n:
            dp[li]+=dpsum[i]
            dp[li]=dp[li]%998244353
        if ri<=n:
            dp[ri]-=dpsum[i]
            dp[ri]=dp[ri]%998244353

print(dp[n])

Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
k_list=[]

for i in range(k):
    l,r=map(int,input().split())
    k_list.append([l,r])

dp=[0]*n
dp[0]=1
dpsum=[0]*n
dpsum[0]=1

for i in range(1,n):
    for j in range(k):
        l,r=k_list[j]
        li=i-r
        ri=i-l
        if ri<0:
            continue
        if li<=0:
            dp[i]+=dpsum[ri]
        else:
            dp[i]+=dpsum[ri]-dpsum[li-1]
    dpsum[i]=dpsum[i-1]+dp[i]

print(dp[n-1]%998244353)


Fixed submission:
n,k=map(int,input().split())
k_list=[]

for i in range(k):
    l,r=map(int,input().split())
    k_list.append([l,r])

dp=[0]*(n+1)
dp[1]=1
dpsum=[0]*(n+1)
dpsum[1]=1

for i in range(1,n):
    dpsum[i]=dp[i]+dpsum[i-1]
    for j in range(k):
        l,r=k_list[j]
        li=i+l
        ri=i+r+1
        if li<=n:
            dp[li]+=dpsum[i]
            dp[li]=dp[li]%998244353
        if ri<=n:
            dp[ri]-=dpsum[i]
            dp[ri]=dp[ri]%998244353

print(dp[n])

Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
s=[]
for i in range(k):
    l,r=map(int,input().split())
    for j in range(l,r+1):
        s.append(j)

dp=[0]*n
dp[0]=1

smax=max(s)

for i in range(0,n):
    for j in range(max(0,i-smax),i):
        if i-j in s:
            dp[i]+=dp[j]

print(dp[n-1]%998244353)


Fixed submission:
n,k=map(int,input().split())
k_list=[]

for i in range(k):
    l,r=map(int,input().split())
    k_list.append([l,r])

dp=[0]*(n+1)
dp[1]=1
dpsum=[0]*(n+1)
dpsum[1]=1

for i in range(1,n):
    dpsum[i]=dp[i]+dpsum[i-1]
    for j in range(k):
        l,r=k_list[j]
        li=i+l
        ri=i+r+1
        if li<=n:
            dp[li]+=dpsum[i]
            dp[li]=dp[li]%998244353
        if ri<=n:
            dp[ri]-=dpsum[i]
            dp[ri]=dp[ri]%998244353

print(dp[n])

Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
s=[]
for i in range(k):
    l,r=map(int,input().split())
    for j in range(l,r+1):
        s.append(j)

dp=[0]*n
dp[0]=1

for i in range(0,n):
    for j in range(0,i):
        if i-j in s:
            dp[i]+=dp[j]

print(dp[n-1]%998244353)


Fixed submission:
n,k=map(int,input().split())
k_list=[]

for i in range(k):
    l,r=map(int,input().split())
    k_list.append([l,r])

dp=[0]*(n+1)
dp[1]=1
dpsum=[0]*(n+1)
dpsum[1]=1

for i in range(1,n):
    dpsum[i]=dp[i]+dpsum[i-1]
    for j in range(k):
        l,r=k_list[j]
        li=i+l
        ri=i+r+1
        if li<=n:
            dp[li]+=dpsum[i]
            dp[li]=dp[li]%998244353
        if ri<=n:
            dp[ri]-=dpsum[i]
            dp[ri]=dp[ri]%998244353

print(dp[n])