Handing out candies

Interview

Time limit2sMemory limit512 MB

Summary

For every K, count the ways to choose one candy of each brand 1 through K, and print the total over all K.

Level: Medium5 of 10
Topics: Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

You want to hand out candies to the participants of an algorithm camp.

You have $N$ candies, and every candy has a brand written as an integer.

First you decide $K$ , the number of candies you hand out. Then you pick exactly one candy of each brand from brand $1$ through brand $K$ .

$K$ can be any value from $1$ to $N$ , and two candies of the same brand count as different candies. Write a program that computes the total number of ways to pick the candies, summed over every $K$ .

Input

The first line contains the number of candies $N$ . ( $1 \le N \le 50$ )

The second line contains the brands of the $N$ candies, separated by spaces. Each brand is an integer between $1$ and $50$ .

Output

Print the number of ways to pick the candies on the first line. The value is smaller than $2^{31}$ .

Examples5

Example 1
Input
```
3
1 3 2
```
Expected output
```
3
```
Example 2
Input
```
3
1 1 2
```
Expected output
```
4
```
Example 3
Input
```
8
1 3 2 5 7 4 5 4
```
Expected output
```
9
```
Example 4
Input
```
10
1 1 2 2 3 3 4 4 5 5
```
Expected output
```
62
```
Example 5
Input
```
1
2
```
Expected output
```
0
```