Ayush, Gaurav and Astrologer

Problem Description
Ayush and Gaurav are best friends. Both of them are travelling to a strange city called Algorithmia. During their travel, both of them gets separated. In Algorithmia there are n locations and m directed paths of unit length between these locations
Now Ayush wants to search Gaurav, so he goes to meet the astrologer in the city. Astrologer told him the location of Gaurav but he warns Ayush that he must travel through the path of length between l to r else his friendship might get broken
So you have to help Ayush to count the number of paths of length between l to r between his and Gaurav location so that their friendship does not get broken
The count of paths may be too large, so output the answer modulo (1000000007)
Input
First line contains two integers n, m
Next m lines contains the two integers a and b showing a directed path between a and b
Next line contains the two space separated integers containing Ayush location then Gaurav Location
Next line contains the integer l and r
Output
Output a single line containing the required integer
Constraints
 n ≤ 30
 m ≤ 10^{5}
 1 ≤ a, b ≤ n
 1 ≤ Ayush Location, Gaurav Location ≤ n
 1 ≤ l, r ≤ 10^{9}
 The directed paths can contains selfloops and multiple edges
Subtasks
 Subtask #1: l = r (20 points)
 Subtask #2: r − l ≤ 10^{9} (80 points)
Sample Input
2 3
1 1
1 2
2 2
1 2
3 3
Sample Output
3
Explanation
Let us call edge (1,1) as x, (1,2) as y and (2,2) as z
Then 3 paths are :
1. y,z,z
2. x,y,z
3. x,x,y
Note: Huge I/O, Use scanf/printf instead of cin/cout
Author:  pravinkarma 
Tags  pravinkarma 
Date Added:  21082015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA 
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. 