AT_k2pc001_h4 マシュマロ(Marshmallow)

kagamiz 有一只宠物叫ミズゴロウ，每天他都会带着它从家走 $ K $ 米去公园。在沿途和回来路上，他们会玩一个游戏： - kagamiz 会把棉花糖投掷到前面的 $ 1 $ 米或 $ 2 $ 米处，ミズゴロウ会去接住棉花糖。 - 随后，kagamiz 也会走到投掷的位置，并重复这一操作。 需要注意的是，棉花糖不能被投到超出公园或在家之前的地方。去公园的路上从家（0米）出发，而回家的路上从公园（$ K $ 米）出发，这两个地点他们一定都会经过。然而，去程中有 $ P $ 个位置，回程中有 $ Q $ 个位置，总共有 $ R $ 个位置有水坑。若把棉花糖投掷到这些地方，ミズゴロウ会因为喜欢嬉水而停留，不再前进，因此这些地方不能投。 你的任务是，当给定 $ K $、$ R $ 和水坑位置的信息时，计算出所有可能路径的数量，并输出该数量对 $ 100000 $ 取模的结果。 - $ 1 \leq K \leq 3000000 $：家到公园的距离。 - $ 0 \leq R \leq 100000 $：去程或回程中水坑的总数量。 - $ 1 \leq a_i \leq K $：家到水坑的距离。 - 整数 $ t_i $ 表示水坑位于去程还是回程，取值为 $ 1 $ 或 $ 2 $。 在某些限制条件下： - 对 $ 30\% $ 的数据，满足 $ R = 0 $。 - 对 $ 20\% $ 的数据，满足 $ K \leq 15 $。 - 对 $ 10\% $ 的数据，同时满足上述两个条件。 - 对 $ 40\% $ 的数据，至少满足上述两个条件之一。 请注意，这些限制条件的分数并不等于 $ 100\% $。

第一行包含两个整数 $ K $ 和 $ R $。 接下来的 $ R $ 行中，每行包含两个整数 $ a_i $ 和 $ t_i $，分别表示水坑的位置和路径类型（$ 1 $ 表示去程，$ 2 $ 表示回程）。

输出一个整数，表示所有可能路径的数量对 $ 100000 $ 取模的结果。

- $ 1 \leq K \leq 3000000 $ - $ 0 \leq R \leq 100000 $ - $ 1 \leq a_i \leq K $ - $ t_i \in \{1, 2\} $ **本翻译由 AI 自动生成**