Waterpark

Το τοπικό υδάτινο πάρκο διαθέτει ένα μεγάλο συγκρότημα από τσουλήθρες με πολλές διαδρομές, που διασταυρώνονται κατά την κάθοδο. Υπάρχει ένα σημείο εκκίνησης και ένα σημείο τερματισμού, αλλά σε διάφορα σημεία μπορεί κανείς να στρίψει και να ακολουθήσει διαφορετικές διαδρομές. Ο Walter και η Wanda αναρωτιούνται πόσες ακριβώς διαφορετικές διαδρομές υπάρχουν που μπορεί να ακολουθήσει κανείς και να κατέβει την τσουλήθρα. Μπορείτε να λύσετε την απορία τους;

Πιο συγκεκριμένα, υπάρχουν ~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~, όπου ~1 \le x < y \le n~. Για παράδειγμα, το ζεύγος ~1234\;8765~ δηλώνει μια απευθείας τσουλήθρα που ενώνει το σημείο ~1234~ με το σημείο ~8765~. Η τελευταία γραμμή της εισόδου θα υποδεικνύεται από το ζεύγος σημείων ~0\;0~.

Έξοδος

Η έξοδος θα είναι ένας ακέραιος αριθμός, ο αριθμός των διαφορετικών διαδρομών από το σημείο ~1~ στο σημείο ~n~. Μπορείτε να υποθέσετε ότι ο αριθμός των διαδρομών θα είναι μικρότερος από ~2^{30}~. Είναι πιθανό να μην υπάρχει καμία διαδρομή από το σημείο ~1~ στο σημείο ~n~, οπότε ο αριθμός των διαδρομών θα είναι ~0~.

Παράδειγμα

input

4
1 2
1 4
2 3
2 4
3 4
0 0

output

3