Sum of Products of Subsets Given an integer k and a list of integers A of size n, find the product of all subsets in A of size k and sum them together.

For example,

k = 2
n = 4
A = 1 2 3 4


The subsets of size 2 and their products are

1 2 = 2
1 3 = 3
1 4 = 4
2 3 = 6
2 4 = 8
3 4 = 12


which sum together to 35.

Some test cases:

Input

A = 73 36 86 76 5 25 15 95 27 1
n = 10
k = 4

A = 7 16 56 83 14 97 71 24 65 32 75 61 64 73 94 34 10
n = 17
k = 3


Output

499369377

87409828


The input can be in whatever format suits your language best. You can have, for example, the variables A, n, and k set to the input already. The integers in A are not necessarily unique.

Constraints

Functions which solve this question are not allowed, as well as functions which generate subsets. Also, to avoid Θ(n^k) submissions, if a solution is made using a better approach, it will have a -30 character bonus. (-30 is subject to change)

The shortest solution is the winner.

Side Note: It's okay to post solutions which do not follow the rules if it demonstrates the strengths of your language. It just won't be part of the scoring.

For example, 

Mathematica (31)

Times@@#&amp;/@A~Subsets~{k}//Total
R - 20

Since the OP said:

Side Note: It's okay to post solutions which do not follow the rules if it demonstrates the strengths of your language. It just won't be part of the scoring.

sum(combn(A,k,prod))