Cake slices

Interview

Time limit1sMemory limit1024 MB

Summary

Given up to 10 cake slices, where slice i is 1/c_i of a cake, count the subsets whose total size is between 99/100 and 101/100 of a cake.

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

Problem

Anz received a lot of slice cakes as a birthday present.

After eating cake and feeling happy, Anz realized that the leftover cake had to be cleaned up and put in the refrigerator, which is a tedious chore.

In the end, Anz found a good way to tidy up. Gather the remaining cake slices and combine them into one whole cake! If the sizes of the chosen slices add up to at least $\frac{99}{100}$ of a cake and at most $\frac{101}{100}$ of a cake, they can be gathered into one whole cake.

Then Anz wondered how many ways there are to choose slices that can be made into one whole cake. At that moment, though, Anz became very tired of the job, so Anz asked you to solve it.

Input

The first line contains the number of leftover cake slices $N$ .

The second line contains integers $c_i$ separated by spaces. Slice $i$ is $\frac{1}{c_i}$ of a cake.

Output

Print the number of ways to choose slices such that all of the chosen slices together make one whole cake.

Constraints

$1 \le N \le 10$

$2 \le c_i \le 25$

Examples2

Example 1
Input
```
6
3 4 6 7 9 10
```
Expected output
```
2
```
Example 2
Input
```
10
2 2 4 4 4 4 8 8 8 8
```
Expected output
```
94
```