410010: GYM103896 L Dog and Friends
Description
The Dog is a Tier 3 Pet, available in the Standard Pack and Expansion 1. Whenever a friend is summoned, the Dog will either gain Attack or Health. The stat raised will be chosen at random. If the friend is summoned in battle, the stat boost will only last for that battle; but if the friend is summoned outside of battle, the stat boost will be permanent. - Super Auto Pets Wiki
The $$$N$$$ creatures in the world of Super Auto Pets are friends with some number (possibly 0) of other pets in the world. Each pet is labeled with a unique integer ID between $$$0$$$ and $$$N-1$$$ (inclusive). After being knocked out by a pet with far higher stat boosts, the dog (whose unique ID is 0) has forgot how many friends they have. However, the dog has been able to ask how many friendships (which are bidirectional among animals) each of the other $$$N-1$$$ creatures has within the world. The dog would like to know the number of possibilities for the number of friends they have given what they know about the number of friends all other creatures have.
InputThe first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^6$$$) that represents the number of pets in the world of Super Auto Pets. The second line of input contains $$$N-1$$$ space-separated integers $$$f_i$$$ ($$$1 \leq i < N$$$, $$$0 \leq f_i < N$$$) that represent the number of other pets creature $$$i$$$ is friends with in the world.
OutputPrint a single integer representing the number of possibilities for the number of friends the dog has.
ExamplesInput3 2 2Output
1Input
3 1 1Output
2Input
3 0 2Output
0