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
  
  INF = 1 << 60
  MOD = 998244353
  sys.setrecursionlimit(2147483647)
  input = lambda: sys.stdin.readline().rstrip()
  
  
  class SegmentTree(object):
      def __init__(self, A, dot, unit):
          n = 1 << (len(A) - 1).bit_length()
          tree = [unit] * (2 * n)
          for i, v in enumerate(A):
              tree[i + n] = v
          for i in range(n - 1, 0, -1):
              tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
          self._n = n
          self._tree = tree
          self._dot = dot
          self._unit = unit
  
      def __getitem__(self, i):
          return self._tree[i + self._n]
  
      def update(self, i, v):
          i += self._n
          self._tree[i] = v
          while i != 1:
              i >>= 1
              self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])
  
      def add(self, i, v):
          self.update(i, self[i] + v)
  
      def sum(self, l, r):
          l += self._n
          r += self._n
          l_val = r_val = self._unit
          while l < r:
              if l & 1:
                  l_val = self._dot(l_val, self._tree[l])
                  l += 1
              if r & 1:
                  r -= 1
                  r_val = self._dot(self._tree[r], r_val)
              l >>= 1
              r >>= 1
          return self._dot(l_val, r_val)
  
  
  def resolve():
      n, k = map(int, input().split())
  
      tree = SegmentTree([0] * n, lambda x, y: (x + y) % MOD, 0)
      tree.update(0, 1)
      D = [tuple(map(int, input().split())) for _ in range(k)]
  
      for i in range(1, n):
          for l, r in D:  # [i - r, i - l]
              if i - l >= 0:
                  tree.add(i, tree.sum(i - r, i - l + 1))
      print(tree[n - 1] % MOD)
  
  
  resolve()
  
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."}]