Problem 1071 --妹妹与楼梯

1071: 妹妹与楼梯

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 65  Solved: 11
[Submit][Status][Web Board][Creator:]

Description

在HHU有一栋高耸入云的建筑叫做致用楼,妹妹们平时在这栋楼上课。致用楼一共有N阶台阶,妹妹们每次只会上一级或两级台阶。这样的话,对于3阶台阶的致用楼,妹妹们一共就有3种上楼的方式{ (1, 1, 1), (2, 1), (1, 2)}。当然啦,在这个充满魔法的世界里,这些台阶有一些不同寻常的地方。某些台阶具有传送能力,一旦妹妹们踏上这些台阶,就会被传送到某个指定的台阶上。当然了,众所周知的是爬台阶是一件非常辛苦的事情,所以这种传送能力不会把妹妹们送到当前台阶的下方,也不会传送至原地不动,显然也不会传送到比最高的一级台阶更高的地方,否则妹妹们会非常生气的。现在,妹妹们知道了今天致用楼一共有多少级台阶,并且知道了某些具有传送能力台阶的传送终点,问一共有多少种方式走到最高的台阶。注意,如果妹妹踏上了带传送能力的台阶,一定会被传送,你可以理解为妹妹目前在第0级台阶(地面),目标是到第N级台阶上。

Input

首先输入两个整数N,M,分别表示最高的台阶为N,一共有M个传送点。
接下来M行,每行两个整数P Q,表示一旦踏上了台阶P,那么会被立即传送到台阶Q。
输入保证N,M<=100000, 1<=P<Q<=100000

Output

一个整数,表示一共有多少种到达第N级台阶的方式,由于输出过大,你只需要输出结果对100000007取模的结果。

Sample Input

3 2
1 2
2 3

Sample Output

2

HINT

注意每个传送点的目标是唯一的,但是某个点可以作为多个传送点的目标位置。

Source

[Submit][Status]