워터파크

동네 워터파크에는 언덕을 따라 여러 갈래로 교차하며 내려가는 훌륭한 미끄럼틀 단지가 있다. 출발점과 도착점은 각각 하나뿐이지만, 중간의 여러 지점에서 방향을 틀어 다른 길로 갈 수 있다. 월터와 완다는 미끄럼틀을 타고 내려가는 서로 다른 경로가 정확히 몇 가지인지 궁금해한다. 이들의 문제를 풀 수 있겠는가?

좀 더 정확히 말하면, 길이 갈라지거나 합쳐지는 지점이 $n$개 있고 각각 번호가 매겨져 있다(출발점은 $1$번, 도착점은 $n$번). 모든 길은 언덕 아래쪽, 즉 더 큰 번호의 지점으로만 향한다. 어떤 길은 서로 만나지 않고 교차하기도 하지만 그런 경우는 신경 쓰지 않아도 되고, 미끄럼틀을 타는 사람들 사이의 충돌도 고려하지 않는다. 우리가 풀어야 할 것은 단지 언덕을 따라 내려가며 거칠 수 있는 서로 다른 지점 번호 수열이 몇 가지인지 세는 것이다.

예를 들어 어떤 작은 워터파크에 지점이 $4$개 있고, $1$번에서 $2$번과 $4$번으로, $2$번에서 $3$번과 $4$번으로, $3$번에서 $4$번으로 가는 직행 미끄럼틀이 있다고 하자. 내려가는 방법은 $3$가지다: $(1,2,3,4)$, $(1,2,4)$, $(1,4)$로 갈 수 있다.

힌트: 미끄럼틀의 맨 아래에서부터 거꾸로 생각해 보라.

첫 번째 줄에 지점의 개수를 나타내는 정수 $n$ ($1 \le n \le 9999$)이 주어진다. 이어지는 각 줄에는 x y 형태의 지점 쌍이 주어지며, 이는 $x$번 지점에서 $y$번 지점으로 가는 직행 미끄럼틀을 뜻한다($1 \le x < y \le n$). 예를 들어 1234 8765는 $1234$번 지점에서 $8765$번 지점으로 가는 직행 미끄럼틀을 나타낸다. 입력의 마지막은 지점 쌍 0 0으로 표시된다.

$1$번 지점에서 $n$번 지점까지의 서로 다른 경로의 수를 정수 하나로 출력한다. 이 값은 $2^{30}$보다 작다고 가정해도 된다. $1$번 지점에서 $n$번 지점으로 가는 경로가 하나도 없을 수도 있으며, 이 경우 경로의 수는 $0$이다.