beecrowd | 1954

# Possible Evolutionary Paths

By Leandro Zatesko, UFFS Brazil

Timelimit: 1

Since you are a biologist, could you define the concept of ‘species’?

Laura is a biologist very interest in Computing. Recently she has written a program that, given the genetic codes of two individuals A and B, decides if A is a possible genetic parent of B, which means that there is nothing on the genetic codes of both individuals allowing us to affirm for sure that B has not been generated by A. Note that, if A is a possible genetic parent of B, it does not mean that B belongs to the same species as A, for a mutation might has happened during the generation of B. Naturally, we say that an individual A is a possible genetic ancestor of an individual B if there is a sequence of k individuals I1, I1, …, Ik such that I1 = A, Ik = B and, for every j ∈ {1, …, k - 1}, Ij is a possible genetic parent of Ij + 1.

Laura is studying the fossils found last month in Chapecó in order to determine, through the extracted genetic codes, the species that used to live in the region. But the concept of ‘species’ is very controversial. Laura, who does not want to live situations like the one of the madam in the image above, has preferred adopting the following definition: two individuals A and B belong to the same species if and only if A is a possible genetic ancestor of B and B is a possible genetic ancestor of A. The diagram below illustrates a situation with 7 fossilised individuals, in which an arc from an individual A to an individual B represents that A is a possible genetic parent of B. In the example, we can identify 3 species: I, II and III.

Given the informations provided by Laura's program, help her to calculate the number of possible evolutionary paths from the species of an individual S to the species of an individual T. A possible evolutionary path from a species E1 to a species Ek is a sequence of k species E1, E2, …, Ek such that, for every j ∈ {1, …, k - 1}, there is some individual B belonging to the species Ij + 1 which has a possible genetic parent belonging to the species Ij.

## Input

The first input line consists of 4 integers, N, M, S e T (1 ≤ N ≤ 105, 0 ≤ M ≤ 106, 1 ≤ S, TN), wherein N is the number of fossilised individuals, designated by the integers from 1 to N, whose genetic codes have been obtained by Laura. Each one of the M lines following consists of 2 integers, A and B (1 ≤ A, BN), representing that Laura's program considers the individual A a possible genetic parent of B.

## Output

Your program shall output a line containing a single integer, which shall represent the number of possible evolutionary paths from the species to which the individual S belongs to the species to which the individual T belongs. As this number can be very large, your program shall output only the remainder this number leaves when divided by 109 + 7.

 Input Samples Output Samples 7 10 1 7 1 2 2 1 2 3 3 4 4 5 5 3 3 6 2 6 6 7 7 6 2
 7 10 7 4 1 2 2 1 2 3 3 4 4 5 5 3 3 6 2 6 6 7 7 6 0
 7 10 1 7 1 2 2 1 3 2 3 4 4 5 5 3 3 6 2 6 6 7 7 6 1
 5 8 1 5 1 2 1 3 1 4 2 3 2 4 2 5 3 5 4 5 5