← 返回题目列表

AtCoder · k2pc001_h4

D. 棉花糖

中文机器翻译题面 查看原题

問題文

Kagamiz 每天都会从家里带他的宠物 Sphagnum。 K m 我正在散步到一个远处的公园。
此时,Kagamiz 在去程和回程中与 Mizugorou 进行以下游戏:

  • 1 领先吗? 2 m 先扔棉花糖,水五郎接住它。
  • Kagamiz也会移动到你扔它的地方并重复相同的操作。

但是,目前不允许在公园后面或房子前面的某个地方扔棉花糖。
此外,出境旅行的起点是从家里。 0 m点,回程起点是从家 K 这是m的一个点,你一定要去这里。
然而,在出境旅行中 P 点,出回程 Q 位置,总计 R 位置有水坑, 棉花糖被打湿了,泥炭藓五郎在水坑里玩耍,无法从那里移动。
因此,不要将棉花糖扔到有水坑的地方。

在这种情况下,Kagamiz 和 Mizugorou 有多少种方法可以在所有地点扔棉花糖并散步?

你的工作是, K , R ,并且当给出有关水坑位置的信息时, K m 在所有点扔棉花糖并计算步行的路数。 目的是告诉kagamiz除以 100000 后的余数。 在


入力

K R
t_1 a_1
t_2 a_2
.
.
.
t_R a_R
  • 1 行中,一个整数 K , R 以空格作为分隔符。
  • 继续 来自行 R 行包含有关水坑的信息。
    i + 1 行目 (1 ≦ i ≦ R) 有, 在 1, 2 中的任意整数之后,有一个整数 a_i 以空格分隔。
    i + 1 行中的第一个数字是 当 1 (t_i = 1) ,从家里出去的路上 a_i 表示距离米远有一个水坑,
    i + 1 行中的第一个数字是 当 2 (t_i = 2) 从家回来的路上 a_i 表示米开外有一个水坑。

出力

在给定条件下,步行的方式数, 打印除以 100000 后的余数。

制約

  • 1 ≦ K ≦ 3000000 从房子到公园的距离
  • 0 ≦ R ≦ 100000 去程或回程的水坑总数
  • 1 ≦ a_i ≦ K  从房子到水坑所在点的距离
  • 表示去程或回程的整数。 t_i 必须是 1,2 。

部分点

积分分配 30% 分钟, R = 0 很满意。 在
积分分配 20% 分钟, K ≦ 15 很满意。 在
积分分配 10% 分钟内,这些 2 两个条件均满足。
积分分配 40% 分钟内,这些 2 至少满足以下条件之一。 请注意,这并不意味着
※30%+20%+10%+40%=100%。


入力例 1

3 0

出力例 1

7

入力例 2

14 2
1 9
2 3

出力例 2

7105

入力例 3

1 1
2 1

出力例 3

0
回程起点必须是 K 请注意,这是点 m。

入力例 4

3 2
1 1
2 1

出力例 4

0
在此输入/输出示例中,从家里 1 去程和回程距离米处都有一滩水。
因此,由于不可能访问所有地点, 输出 0 。

(故事)kagamiz
(问题)kagamiz
(测试仪)fura2