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 pi1∗pi2∗…∗pim
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:
Useful Links:
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.