import sys input = lambda : sys.stdin.readline().rstrip() write = lambda x: sys.stdout.write(x+"\n") debug = lambda x: sys.stderr.write(x+"\n") writef = lambda x: print("{:.12f}".format(x)) ### 遅延評価セグメント木(はやい非DFS) class LSG: def __init__(self,n, a=None): self._n = n self._ninf = ninf self._op = op self._mapping = mapping self._composition = composition self._f0 = f0 x = 0 while (1 << x) < self._n: x += 1 self._log = x self._size = 1 << self._log self._d = [self._ninf] * (2 * self._size) self._lz = [self._f0] * self._size if a is not None: for i in range(self._n): self._d[self._size + i] = a[i] for i in range(self._size - 1, 0, -1): self._update(i) def check(self): return [self.query_point(p) for p in range(self._n)] def update_point(self, p, x): p += self._size for i in range(self._log, 0, -1): self._push(p >> i) self._d[p] = x for i in range(1, self._log + 1): self._update(p >> i) def query_point(self, p): p += self._size for i in range(self._log, 0, -1): self._push(p >> i) return self._d[p] def query(self, left, right): if left == right: return self._ninf left += self._size right += self._size for i in range(self._log, 0, -1): if ((left >> i) << i) != left: self._push(left >> i) if ((right >> i) << i) != right: self._push(right >> i) sml = self._ninf smr = self._ninf while left < right: if left & 1: sml = self._op(sml, self._d[left]) left += 1 if right & 1: right -= 1 smr = self._op(self._d[right], smr) left >>= 1 right >>= 1 return self._op(sml, smr) def query_all(self): return self._d[1] def update(self, left, right, f): if right is None: p = left p += self._size for i in range(self._log, 0, -1): self._push(p >> i) self._d[p] = self._mapping(f, self._d[p]) for i in range(1, self._log + 1): self._update(p >> i) else: if left == right: return left += self._size right += self._size for i in range(self._log, 0, -1): if ((left >> i) << i) != left: self._push(left >> i) if ((right >> i) << i) != right: self._push((right - 1) >> i) l2 = left r2 = right while left < right: if left & 1: self._all_apply(left, f) left += 1 if right & 1: right -= 1 self._all_apply(right, f) left >>= 1 right >>= 1 left = l2 right = r2 for i in range(1, self._log + 1): if ((left >> i) << i) != left: self._update(left >> i) if ((right >> i) << i) != right: self._update((right - 1) >> i) def _update(self, k): self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1]) def _all_apply(self, k, f) -> None: self._d[k] = self._mapping(f, self._d[k]) if k < self._size: self._lz[k] = self._composition(f, self._lz[k]) def _push(self, k): self._all_apply(2 * k, self._lz[k]) self._all_apply(2 * k + 1, self._lz[k]) self._lz[k] = self._f0 def loc(self, l, r): return self._lz[self._size+l : self._size+r] ninf = 0 f0 = None def op(x,y): return (x+y)%M def mapping(f,x): if f is None: return x return f # composition: あとからきたクエリがf1に入る def composition(f1,f2): if f2 is None: return f1 elif f1 is None: return f2 return f1 # class LSG: # def __init__(self, n, v): # self.n = n # self.cum = [0] # self.low = 0 # self.total = 0 # for vv in v: # self.cum.append(cum[-1]+vv) # def update(self, l, r, f): # if f==0: # # [l:r) を 0 にする # self.total += self.query(l,r) # else: # self.cum[r] = self.cum[r-1] + f # def query(self, l, r): # # [l,r) の区間和 # return self.cum[r] - self.cum[l] - n,k = list(map(int, input().split())) m = int(input()) lr = [] for i in range(m): lr.append(tuple(map(lambda i: int(i), input().split()))) index = list(range(m)) index.sort(key=lambda i: (lr[i][1], -lr[i][0])) dp = [[0]*(k+1) for _ in range(k+1)] dp[0][0] = 1 cum = [LSG(k+1, dp[i]) for i in range(k+1)] low = 0 ind = 0 M = 998244353 N = k+10 # 必要なテーブルサイズ g1 = [0] * (N+1) # 元テーブル g2 = [0] * (N+1) #逆元テーブル inverse = [0] * (N+1) #逆元テーブル計算用テーブル g1[0] = g1[1] = g2[0] = g2[1] = 1 inverse[0], inverse[1] = [0, 1] for i in range( 2, N + 1 ): g1[i] = ( g1[i-1] * i ) % M inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより g2[i] = (g2[i-1] * inverse[i]) % M def cmb(n, r, M=M): if ( r<0 or r>n ): return 0 r = min(r, n-r) return ((g1[n] * g2[r] % M) * g2[n-r]) % M def perm(n, r, M=M): if (r<0 or r>n): return 0 return (g1[n] * g2[n-r]) % M for r in range(1,k+1): while ind