問題文
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 表示米开外有一个水坑。
出力
制約
- 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
(问题)kagamiz
(测试仪)fura2