Kata

This kata is looking for a more effective algorithm to the same problem as in its easy version.

---

We are given an array [a[0], a[1], a[2], ...] of odd length.

Your task is to calculate the sum of products a[i0]*a[i1]*..a[ik] for all possible even-odd-even increasing index sequence i0, i1, i2, ... of odd length.

More explicitly, we have to form the product of a[i_]'s for all the following index sequences:

1. i0 < i1 < i2 < i3 < i4 < ... < ik,
2. k is even (hence the length of the index sequence is odd),
3. i0,i2,i4,... must be even, and i1,i3,i5,... must be odd.

Examples

If the full index set is 0,1,2,3,4 (i.e. length of array is 5), we have to take the following index sequences:
[0], [2], [4], [0,1,2], [0,1,4], [0,3,4], [2,3,4] and [0,1,2,3,4].

On the following specific inputs, we expect:

sum_of_prods([1,2,5]) = 1 + 5 + 1*2*5 = 16
sum_of_prods([2,4,6,8,10]) = ( 2 + 6 + 10 
                             + 2*4*6 + 2*4*10 + 2*8*10 + 6*8*10
                             + 2*4*6*8*10 ) = 4626

Note. You have to find an algorithm efficient enough so that the submit testcases would not timeout.

---

For your convenience, a prod function is predefined which inputs an array of numbers and returns their product.