# 0046. Sum of Products

Input file name: | sumprod.in |

Output file name: | sumprod.out |

Time limit: | 1 s |

Memory limit: | 64 megabytes |

Of course you know that there are **C ^{k}_{n}** ways to select

**k**numbers from a set of

**n**. Given a set of

**n**integer numbers, Anton for each such combination calculates its total product and then sums all products.

For example, if the numbers are **(2, 2, 3)**, **k=2** and **n=3** he will get
**2⋅ 2+2⋅ 3+2⋅ 3=16**.

Your task is to calculate the answer he will get.

Input file

The first line of the input file contains two integer numbers **n** and **k** (**1≤ k≤ n≤ 200**).
The second one contains **n** non-negative integer numbers. These numbers will not be greater than
32000.

Output file

Output only one integer number – sum of all products by **k**.

Examples:

sumprod.in | sumprod.out |
---|---|

3 2 2 2 3 | 16 |

*Source: Petrozavodsk training camp, Summer 2002. Conclusive contest*

*Author: Andrew Lopatin, Nick Durov*

Discuss Submit a solution

Printable version