queue

时间限制:1s      空间限制:128MB

题目描述

自从小C接过宇宙大总统的职位后,为了巩固自己的统治,他决定给全宇宙的精英排个队,这样,下次聚集精英们的时候,不至于乱成一锅粥。
当然,精英们可是非常挑剔的,它们对于排队可有很苛刻的要求。
为了方便描述,n个精英,被编号1~n。排完队之后,每个精英要求,自己的后面(不必是严格后面)都必须有一个人的编号和自己的编号相差为1(+1或-1);
而且,有很多特别霸气的精英,比如Mars之类的人,他们认为自己只能站在队伍的某个位置,小C必须满足他们的需求。
小C想知道,存在多少方案满足精英们如此苛刻的条件。


输入格式

第一行: 两个正整数n, k,表示有n个精英,k个人强制要求自己的位置。
第2~k+1行,两个整数a,b,表示编号为a的精英要求自己站在队伍的第b个位置;


输出格式

 一个整数,输出方案, 答案对10^9+7 取模


样例输入

5 2
1 1
2 3

样例输出

2


提示

【样例解释】
两种方案为:
1 5 2 3 4
1 5 2 4 3 
最后一个人由于后面没有人,所以不要求后面有人和他编号相差为1
强行要求位置的人,他的后面也必须有人和他编号相差为1(除非他是最后一个)
【数据约定】
 100% n <= 100000, k<=n;


题目来源

没有写明来源