output_description: Print the number of ways for Tak to go from Cell 1 to Cell N, modulo
  998244353.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N K
      L_1 R_1
      L_2 R_2
      :
      L_K R_K
attempt: import sys
  
  input = sys.stdin.readline
  N, K = map(int, input().split())
  LR = [list(map(int, input().split())) for _ in range(K)]
  P = 998244353
  
  
  class SegmentTree:
      def __init__(self, n, segfunc=min, ele=10**10):
          self.ide_ele = ele
          self.num = pow(2, (n - 1).bit_length())
          self.seg = [self.ide_ele] * 2 * self.num
          self.segfunc = segfunc
  
      def init(self, init_val):
          # set_val
          for i in range(len(init_val)):
              self.seg[i + self.num - 1] = init_val[i]
          # built
          for i in range(self.num - 2, -1, -1):
              self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])
  
      def update(self, k, x):
          k += self.num - 1
          self.seg[k] = x
          while k:
              k = (k - 1) // 2
              self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])
  
      def query(self, p, q):
          if q <= p:
              return self.ide_ele
          p += self.num - 1
          q += self.num - 2
          res = self.ide_ele
          while q - p > 1:
              if p & 1 == 0:
                  res = self.segfunc(res, self.seg[p])
              if q & 1 == 1:
                  res = self.segfunc(res, self.seg[q])
                  q -= 1
              p = p // 2
              q = (q - 1) // 2
          if p == q:
              res = self.segfunc(res, self.seg[p])
          else:
              res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
          return res
  
  
  dp = SegmentTree(N, segfunc=lambda x, y: x + y % P, ele=0)
  dp.update(0, 1)
  for i in range(1, N):
      tmp = 0
      for l, r in LR:
          tmp = (tmp + dp.query(max(0, i - r), max(0, i - l + 1))) % P
      dp.update(i, tmp)
  print(dp.seg[N - 1 + dp.num - 1])
  
problem_description: Statement
  
  There are N cells arranged in a row, numbered 1, 2, \ldots, N from left to
  right.
  
  Tak lives in these cells and is currently on Cell 1. He is trying to reach
  Cell N by using the procedure described below.
  
  You are given an integer K that is less than or equal to 10, and K non-
  intersecting segments [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K]. Let S be the
  union of these K segments. Here, the segment [l, r] denotes the set consisting
  of all integers i that satisfy l \leq i \leq r.
  
    * When you are on Cell i, pick an integer d from S and move to Cell i + d. You cannot move out of the cells.
  
  To help Tak, find the number of ways to go to Cell N, modulo 998244353.
samples: [{"input": "5 2\n    1 1\n    3 4", "output": "4\n    \n\nThe set S is the union of the segment [1, 1] and the segment [3, 4], therefore\nS = \\\\{ 1, 3, 4 \\\\} holds.\n\nThere are 4 possible ways to get to Cell 5:\n\n  * 1 \\to 2 \\to 3 \\to 4 \\to 5,\n  * 1 \\to 2 \\to 5,\n  * 1 \\to 4 \\to 5 and\n  * 1 \\to 5.\n\n* * *"}, {"input": "5 2\n    3 3\n    5 5", "output": "0\n    \n\nBecause S = \\\\{ 3, 5 \\\\} holds, you cannot reach to Cell 5. Print 0.\n\n* * *"}, {"input": "5 1\n    1 2", "output": "5\n    \n\n* * *"}, {"input": "60 3\n    5 8\n    1 3\n    10 15", "output": "221823067\n    \n\nNote that you have to print the answer modulo 998244353."}]