John and Mary attend a single party. There are n, where 2 ≤ n ≤ 1000, people in the party. John would like to tell a joke to Mary. However, due to some unexpected reason, he cannot tell his joke to Mary by himself. Therefore, he needs somebodies’ help to forward the joke. In this party, Participant A can forward a heard message to Participant B if A is B’s friend and elder than B. In particular, we use a forwarding-pair “A B” to mean that A is B’s friend and elder than B. Given the forwarding-pairs among all the participants, your goal is to compute the number of different ways that John can forward his joke to Mary (note: two ways are different if for the participants involved in both ways, there is at least one participant who is involved in only one way; moreover, k(≥ 2) ways are said to be different if any two ways from the k ways are different). In addition, if no such a way exists, the answer is 0.

For convenience, we use nature numbers 1, 2, . . . , n to present n peoples, in which 1 represents John and n represents Mary. In addition, an input pair i j is a forwarding-pair. Given the number n and a set of forwarding-pairs, your task is to write a computer program to compute the desired value.