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

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

mod=998244353





dp=[1]

imos=[0]*(2*n+10)

imos[0]=1

imos[1]=-1

for i in range(n):

    for l,r in lst:

        imos[i+l]+=dp[-1]

        imos[i+r+1]-=dp[-1]

    dp.append((dp[-1]+imos[i+1])%mod)





print((dp[n-1]))
n,k=list(map(int,input().split()))

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

mod=998244353



dp=[0]*(2*n+10)

dp[0]=1

dp[1]=-1

for i in range(n):

    for l,r in lst:

        dp[i+l]+=dp[i]

        dp[i+r+1]-=dp[i]

    

    dp[i+1]+=dp[i]

    dp[i+1]%=mod





print((dp[n-1]))
n, k = list(map(int, input().split()))
lst = [list(map(int, input().split())) for i in range(k)]
mod = 998244353
dp = [1]
imos = [0] * (2 * n + 10)
imos[0] = 1
imos[1] = -1
for i in range(n):
    for l, r in lst:
        imos[i + l] += dp[-1]
        imos[i + r + 1] -= dp[-1]
    dp.append((dp[-1] + imos[i + 1]) % mod)
print((dp[n - 1]))

n, k = list(map(int, input().split()))
lst = [list(map(int, input().split())) for i in range(k)]
mod = 998244353
dp = [0] * (2 * n + 10)
dp[0] = 1
dp[1] = -1
for i in range(n):
    for l, r in lst:
        dp[i + l] += dp[i]
        dp[i + r + 1] -= dp[i]
    dp[i + 1] += dp[i]
    dp[i + 1] %= mod
print((dp[n - 1]))

-dp = [1] -imos = [0] * (2 * n + 10) -imos[0] = 1 -imos[1] = -1 +dp = [0] * (2 * n + 10) +dp[0] = 1 +dp[1] = -1 -        imos[i + l] += dp[-1] -        imos[i + r + 1] -= dp[-1] -    dp.append((dp[-1] + imos[i + 1]) % mod) +        dp[i + l] += dp[i] +        dp[i + r + 1] -= dp[i] +    dp[i + 1] += dp[i] +    dp[i + 1] %= mod