Số cách hoàn thành trò chơi

Submit solution
Points: 3
Time limit: 1.0s
Memory limit: 256M
Author:
khiemveryimportantpersonprofessional
Problem types
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Khiêm mới tải về một trò chơi. Vì di chuyển qua từng cấp độ rất lâu nên Khiêm quyết định nạp VIP từ khi bắt đầu chơi. Sau khi nạp VIP, trò chơi đã cho Khiêm những cánh cổng dịch chuyển cấp độ. Khiêm thắc mắc trò chơi tặng những cánh cổng này thì mình sẽ có bao nhiêu cách hoàn thành trò chơi?

Một trò chơi có n cấp độ, được kết nối bởi m dịch chuyển tức thời, và nhiệm vụ của bạn là đi từ cấp độ 1 đến cấp n.

Mọi người hãy giúp Khiêm giải quyết vấn đề này, biết rằng bản đồ trò chơi đã được thiết kế để không có chu trình có hướng.

Đầu vào

Dòng đầu tiên có hai số nguyên n và m: số lượng cấp độ và số cổng dịch chuyển tức thời.

m dòng tiếp theo là những dòng mô tả những cổng dịch chuyển tức thời.

Mỗi dòng có hai số nguyên a và b: cổng dịch chuyển tức thời từ cấp a đến cấp độ b.

Đầu ra

In ra một số nguyên: số cách bạn có thể hoàn thành trò chơi. Vì kết quả có thể lớn hãy chia dư 1000000007.

Giới hạn

1≤n≤105, 1≤m≤2∗105, 1≤a,b≤n.

Ví dụ

Đầu vào:

Copy
4 5
1 2
2 4
1 3
3 4
1 4

Đầu ra:

Copy
3

Comments