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

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

为了方便描述，n个精英，被编号1~n。排完队之后，每个精英要求，自己的后面（不必是严格后面）都必须有一个人的编号和自己的编号相差为1（+1或-1）；

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

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

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

第2~k+1行，两个整数a，b，表示编号为a的精英要求自己站在队伍的第b个位置；

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

【样例解释】

两种方案为：

1 5 2 3 4

1 5 2 4 3 

最后一个人由于后面没有人，所以不要求后面有人和他编号相差为1

强行要求位置的人，他的后面也必须有人和他编号相差为1（除非他是最后一个）

【数据约定】

 100% n <= 100000， k<=n;