### Problem Statement

There are some cards in a box which are specified by a String[] cards. One of the operators '+', '-' or '*' is written on the left half of each card and a digit is written on the right half of each card. You draw all cards from the box randomly, one by one. At each step each of the remaining cards has the same probability of being drawn. Then you align the cards from left to right in the order you have drawn them. Finally, add a zero at the left of the cards and calculate the value of this expression. For example, if you have drawn "+1", "-2" and "*3" (in this order), the expression is "0 + 1 - 2 * 3", whose value is -5. Return the expected value.

### Definition

 Class: CalculationCards Method: getExpected Parameters: String[] Returns: double Method signature: double getExpected(String[] cards) (be sure your method is public)

### Notes

-The returned value must have an absolute or relative error less than 1e-9.

### Constraints

-cards will contain between 1 and 50 elements, inclusive.
-Each element of cards will contain exactly 2 characters.
-The first character in each element of cards will be either '+', '-' or '*'.
-The second character in each element of cards will be a digit ('0' - '9').

### Examples

0)

 `{ "+1", "-2", "*3" }`
`Returns: -1.6666666666666667`
 One of the following expressions will be made with equal probability: 0 + 1 - 2 * 3 = -5 0 + 1 * 3 - 2 = 1 0 - 2 + 1 * 3 = 1 0 - 2 * 3 + 1 = -5 0 * 3 + 1 - 2 = -1 0 * 3 - 2 + 1 = -1
1)

 `{ "+1", "+2", "+3" }`
`Returns: 6.0`
 The value will always be 6.
2)

 `{ "+3", "-7", "*4", "+6" }`
`Returns: 3.5`
3)

 `{ "+1", "*2", "*3" }`
`Returns: 3.1666666666666665`
4)

 `{ "*7", "-2", "*0", "+3", "*8" }`
`Returns: 5.633333333333334`
5)

 `{ "+1", "*9", "*9", "*9", "*9", "*9", "*9", "*9", "*9", "*9", "*9" }`
`Returns: 3.5660295009090906E8`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14286&pm=11040

lyrically

#### Testers:

SnapDragon , Rustyoldman , marek.cygan , timmac , ivan_metelsky , Egor

#### Problem categories:

Dynamic Programming, Math