AT_arc182_a [ARC182A] Chmax Rush!

[problemUrl]: https://atcoder.jp/contests/arc182/tasks/arc182_a 長さ $ N $ の整数列 $ S $ があります。はじめ、$ S $ の要素はすべて $ 0 $ です。 また、長さ $ Q $ の整数列 $ P=(P_1,P_2,\dots,P_Q) $ と $ V=(V_1,V_2,\dots,V_Q) $ が与えられます。 すぬけ君は、数列 $ S $ に $ Q $ 回の操作を順に行いたいです。$ i $ 回目の操作は以下です。 - 以下のどちらかの操作を行う。 - $ S_1,S_2,\dots,S_{P_i} $ をすべて $ V_i $ に置き換える。ただし、この操作の前に $ S_1,S_2,\dots,S_{P_i} $ の中に $ V_i $ より真に大きい要素がある場合、すぬけ君は泣き出す。 - $ S_{P_i},S_{P_i+1},\dots,S_N $ をすべて $ V_i $ に置き換える。ただし、この操作の前に $ S_{P_i},S_{P_i+1},\dots,S_N $ の中に $ V_i $ より真に大きい要素がある場合、すぬけ君は泣き出す。 すぬけ君が泣き出さないように $ Q $ 回の操作をすべて行うことのできるような操作列の個数を $ 998244353 $ で割った余りを求めてください。 ただし、$ 2 $ つの操作列が異なるとは、ある $ 1\leq\ i\leq\ Q $ が存在して、$ i $ 番目の操作でどちらの操作を選択したかが異なることを指します。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ P_1 $ $ V_1 $ $ P_2 $ $ V_2 $ $ \vdots $ $ P_Q $ $ V_Q $

答えを整数として出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 5000 $ - $ 1\ \leq\ Q\ \leq\ 5000 $ - $ 1\ \leq\ P_i\ \leq\ N $ - $ 1\ \leq\ V_i\ \leq\ 10^9 $ - 入力はすべて整数 ### Sample Explanation 1 以下のようにするとすぬけ君が泣き出さないように $ 3 $ 回の操作を行うことができます。 - $ S_1 $ を $ 8 $ に置き換える。 - $ S_8 $ を $ 1 $ に置き換える。 - $ S_2,S_3,\dots,S_8 $ を $ 1 $ に置き換える。 これ以外に条件を満たす操作列はないので、$ 1 $ が答えです。例えば、$ 1 $ 回目の操作で $ S_1,S_2,\dots,S_8 $ を $ 8 $ に置き換えると、$ 2 $ 回目の操作でどちらを選んでもすぬけ君が泣き出してしまいます。 ### Sample Explanation 2 $ 2 $ 回目までの操作をどのように行っても $ 3 $ 回目の操作ですぬけ君が泣き出してしまいます。 ### Sample Explanation 3 $ 998244353 $ で割った余りを求めることを忘れないでください。