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 oneway. 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.
Input
The 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.Output
Output a single line containing an integer which is the number of ways in which Chef can travel from P to Q modulo 10^{9}+7.Constraints
 1 ≤ N ≤ 10^{5}
 1 ≤ M ≤ 10^{6}
 1 ≤ P, Q ≤ N
 1 ≤ a, b ≤ N, a != b
Example
Input: 5 6 1 5 1 2 1 3 1 4 1 5 3 4 4 5 Output: 3
Explanation
Possible paths Chef can take are 145, 1345 and 15.Author:  subham_75 
Editorial  https://discuss.codechef.com/problems/CL16BF 
Tags  colg2016, dynamicprogramming, graph, medium, subham_75, topologicalsort 
Date Added:  30092016 
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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 