Chef and Roads
All submissions for this problem are available.
Chef lives in Chefland. Chefland can be accurately represented by a certain number of intersections and the roads connecting them. Chefland is a strange place, because all the roads there are one-way. Also, for any two intersections A and B, once you travel from A to B, you can never return to A again because there is simply no route you can take to get back to A.
Unaware of this, Chef set out to visit his friend, and now he can't return home! So, Chef decides to travel to the townhall and complain about this ridiculous system. Studying the map of Chefland, Chef wonders about the number of ways in which he can travel to the townhall. Help him find this number. As the number may be very large, print it modulo 10^9+7.
InputThe first line of the input contains 2 integers N and M. They are the number of intersections and number of roads in Chefland respectively. The second line contains 2 integers P and Q. P is the intersection where Chef is currently located. Q is the intersection where the townhall is located. M lines follow, each containing a pair of integers a b. For each pair a b, a road exists connecting intersection b to a along which one can travel from a to b only.
OutputOutput a single line containing an integer which is the number of ways in which Chef can travel from P to Q modulo 109+7.
- 1 ≤ N ≤ 105
- 1 ≤ M ≤ 106
- 1 ≤ P, Q ≤ N
- 1 ≤ a, b ≤ N, a != b
Input: 5 6 1 5 1 2 1 3 1 4 1 5 3 4 4 5 Output: 3
ExplanationPossible paths Chef can take are 1-4-5, 1-3-4-5 and 1-5.
|Tags||colg2016, dynamic-programming, graph, medium, subham_75, topologicalsort|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.