Expensive Restraunt

0

0 votes
Easy
Problem

After trading with Ding Ding the broker, you have become very rich. So you decide to give yourself a treat in a 7 star hotel run by Agarwal and Agrawals. Here, there is provision of making your own dish using some ingredients from n special ingredients.The ith ingredient has a price pi and in a dish there has to be exactly m ingredients. The price of dish made by the ingredients i1,i2,im is equal to pi1pi2pim

As you are really happy, you decide to buy every possible dish that can be made. Write a program to output how much money you will have to spend mod 109+7

Hint:
Given an array of n integers. Find the summation of product of all the m sized sub-sequences of the array mod 109+7

Input:

First line of input contains two space separated integers containing n,m . Next line contains n space separated integers in which the ith integer is pi

Output:

Print the answer in a single line.

Constraints:

  1. 1mn103
  2. 1pi105

Useful Links:

  1. Modulo
  2. Sub array / Sub sequence

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

All the possible dishes are [1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4],[3,5],[4,5] where [i,j] means that ith and jth ingredient was taken. Their costs are 20,15,10,5,12,8,4,6,3,2 respectively implying the total cost is 85.

Editor Image

?