Unfriend

Time limit2sMemory limit512 MB

Summary

Count the subsets of nodes in a rooted tree that can be removed, where removing a node forces removal of all its descendants.

Level: Easy2 of 10
Topics: Tree, Brute force, Combinatorics
Solved: No attempts yet

Problem

Mark started a social network by inviting some people. Some of the invitees invited more people, who invited still more, and so on. The network now has $N$ people, numbered from $1$ to $N$ . Person $N$ is Mark himself.

Everyone except Mark was invited by exactly one other person (nobody is invited by more than one person), so the invitations form a tree rooted at Mark.

Mark wants to remove some people from the network and keep the rest. There is one rule: whenever he removes a person, he must also remove everyone that person invited, and everyone those people invited, and so on (that is, the person's entire set of descendants is removed together with them). Mark will never remove himself, and he may also choose to remove nobody.

How many different sets of people can be removed?

Input

The first line contains a single integer $N$ ( $1 \le N \le 6$ ), the number of people. Each of the next $N-1$ lines tells who invited a person: line $i$ ( $1 \le i \le N-1$ ) contains a single integer $j$ ( $i < j \le N$ ), meaning that person $j$ invited person $i$ . Person $N$ is Mark.

Output

Print a single integer: the number of different sets of people that can be removed.

Examples2

Example 1
Input
```
3
3
3
```
Expected output
```
4
```
Example 2
Input
```
4
3
4
4
```
Expected output
```
6
```