### Problem Statement

You are attempting to create a new game that is played by rolling several dice. In order to determine scoring, you need to first know how many different formations can be rolled with those dice. We define a formation as the collection of values that are shown on the dice, without regard to order. Thus, {1, 1, 2}, {1, 2, 1}, and {2, 1, 1} are all the same formation, whereas {1, 1, 2}, {1, 2, 2} and {1, 1, 3} are all different formations. Note that even though two dice may have a different number of sides, for the purpose of counting formations, only the number shown on them matters.

You are given a int[] sides, where the i-th element is the number of sides on the i-th die. The sides of an n-sided die contain all numbers between 1 and n, inclusive. Return the number of different formations that can be made from those dice.

### Definition

 Class: DiceGames Method: countFormations Parameters: int[] Returns: long Method signature: long countFormations(int[] sides) (be sure your method is public)

### Constraints

-sides will contain between 1 and 32 elements, inclusive.
-Each element of sides will be between 1 and 32, inclusive.

### Examples

0)

 `{4}`
`Returns: 4`
 A single die with four sides can have four formations.
1)

 `{2, 2}`
`Returns: 3`
2)

 `{4, 4}`
`Returns: 10`
 Here, there are 10 formations we can make: {1, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 2}, {2, 3}, {2, 4}, {3, 3}, {3, 4}, {4, 4}.
3)

 `{3, 4}`
`Returns: 9`
 Now it is impossible to get {4, 4} because the first die has only 3 sides.
4)

 `{4, 5, 6}`
`Returns: 48`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7601

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10673&pm=7601

timmac

#### Testers:

PabloGilberto , brett1479 , Yarin , Olexiy

#### Problem categories:

Dynamic Programming, Math