Unfriend

Ο Mark προσκάλεσε μερικά άτομα να ενταχθούν στο κοινωνικό του δίκτυο. Κάποιοι από αυτούς προσκάλεσαν νέα άτομα, τα οποία προσκάλεσαν με τη σειρά τους νέα άτομα, και ούτω καθεξής. Τώρα υπάρχουν ~N~ άτομα στο δίκτυο, αριθμημένα από το ~1~ έως το ~N~ . Ο Mark αποφάσισε να αφαιρέσει ορισμένα άτομα και άλλα να τα κρατήσει. Υπάρχει ένας περιορισμός: όταν αφαιρεί ένα άτομο, θα αφαιρέσει επίσης τα άτομα που αυτό προσκάλεσε, και τα άτομα που αυτά προσκάλεσαν, και ούτω καθεξής. Ο Mark δεν θα αφαιρέσει ποτέ τον εαυτό του, και δεν επιτρέπουμε τα ίδια άτομα να προσκαλούνται από περισσότερα από ένα. Ο Mark έχει επίσης τη δυνατότητα να αποφασίσει να μην αφαιρέσει κανέναν.

Πόσα διαφορετικά σύνολα ατόμων μπορούν να αφαιρεθούν;

Είσοδος

Η πρώτη γραμμή εισόδου θα περιέχει έναν ακέραιο αριθμό ~N\;(N \le 6)~, τον αριθμό των ατόμων στο δίκτυο. Ακολουθούν ~N - 1~ γραμμές που μας λένε ποιος προσκάλεσε κάθε άτομο. Για την ακρίβεια, η γραμμή ~i~ σε αυτό το σύνολο ~(1 \le i \le N - 1)~ θα περιέχει έναν ακέραιο αριθμό ~j~ (με ~j > i~), ο οποίος υποδηλώνει ότι το άτομο ~j~ είναι το άτομο που προσκάλεσε το άτομο i. Το άτομο ~N~ είναι ο Mark.

Έξοδος

Εξάγετε έναν ακέραιο αριθμό, τον αριθμό των πιθανών συνόλων ατόμων που μπορούν να αφαιρεθούν.

Παραδείγματα

input

3
3
3

output

4

Επεξήγηση του πρώτου παραδείγματος:

Ο πρώτος αριθμός της εισόδου υποδεικνύει ότι υπάρχουν τρία άτομα στο δίκτυο. Η επόμενη γραμμή μας λέει ότι το άτομο ~1~ προσκλήθηκε από τον Mark, ενώ η τελευταία γραμμή μας λέει ότι το άτομο ~2~ προσκλήθηκε επίσης από τον Mark. Τα σύνολα των ατόμων που μπορούν να αφαιρεθούν είναι ~\left\{ \right\}~, ~\left\{ 1 \right\}~, ~\left\{ 2 \right\}~, ~\left\{ 1,2 \right\}~.

input

4
3
4
4

output

6

Επεξήγηση του δεύτερου παραδείγματος:

Υπάρχουν 4 άτομα στο δίκτυο. Πσρακάτω είναι ένας πίνακας με το ποιος προσκάλεσε ποιον:

Person inviting	Invited
~1~	none
~2~	none
~3~	~1~
~4~	~2,\;3~

Τα πιθανά σύνολα είναι ~\left\{ \right\}~, ~\left\{ 1 \right\}~, ~\left\{ 2 \right\}~, ~\left\{ 1,2 \right\}~, ~\left\{ 1,3 \right\}~ και ~\left\{ 1,2,3 \right\}~. Παρατηρήστε ότι τα σύνολα ~\left\{ 3 \right\}~ και ~\left\{ 2,3 \right\}~ δεν είναι δυνατά, αφού όταν αφαιρείτε το ~3~, πρέπει να αφαιρέσετε και το ~1~.