Big P is willing to climb up a hill. The hill is divided into several checkpoints where the travelers can buy water,food etc for their trip.

At each checkpoint there are several roads that go up to other checkpoints (Not necessarily the next checkpoint).

Now Big P is standing at the base of the hill i.e at checkpoint 1 and wants to know the total number of ways he could climb to the top of the hill i.e the last checkpoint N.

Input Format:
First line contains an integer N,the total number of checkpoints on the hill. Next lines contain a pair of integers (x,y) denoting a directed path from checkpoint x to checkpoint y until a - (0 0) is in the input.

Note: Base of Hill , where Big P is standing is Checkpoint #1 and the top of the hill is Checkpoint #N

Output Format:
A single integer X , denoting the total number of paths from the base of the hill to it's top.

[N<=10000 , 1<=x,y<=N]