logo AlgoBeat OnlineJudge
登录 注册

#104315. [BZOJ 4315] queue

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

自从小 C 接过宇宙大总统的职位后,为了巩固自己的统治,他决定给全宇宙的精英排个队,这样,下次聚集精英们的时候,不至于乱成一锅粥。

当然,精英们可是非常挑剔的,它们对于排队可有很苛刻的要求。

为了方便描述, 个精英,被编号 。排完队之后,每个精英要求,自己的后面(不必是严格后面)都必须有一个人的编号和自己的编号相差为 );

而且,有很多特别霸气的精英,比如 Mars 之类的人,他们认为自己只能站在队伍的某个位置,小 C 必须满足他们的需求。

小 C 想知道,存在多少方案满足精英们如此苛刻的条件。

输入格式

第一行两个正整数 ,表示有 个精英, 个人强制要求自己的位置。

接下来 行,每行两个整数 ,表示编号为 的精英要求自己站在队伍的第 个位置。

输出格式

一行一个整数表示答案对 取模后的值。

样例

样例输入 #1

5 2
1 1
2 3

样例输出 #1

2

样例解释

两种合法方案分别为

数据范围与提示

对于 的数据,