Codeforces Global Round 21 |
---|
Finished |
You are given a positive integer $$$k$$$. For a multiset of integers $$$S$$$, define $$$f(S)$$$ as the following.
More formally, let $$$|S|$$$ denote the number of elements in $$$S$$$. Then,
You are given a multiset of integers, $$$A$$$. Compute $$$\sum\limits_{B\subseteq A} f(B)$$$ modulo $$$10^9+7$$$.
Note that in this problem, we distinguish the elements by indices instead of values. That is, a multiset consisting of $$$n$$$ elements always has $$$2^n$$$ distinct subsets regardless of whether some of its elements are equal.
The first line of input contains two integers $$$n$$$ and $$$k$$$, where $$$n$$$ is the number of elements in $$$A$$$ ($$$1\le k\le n\le 600$$$).
The second line of input contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$, describing the elements in $$$A$$$ ($$$-10^9\le a_i\le 10^9$$$).
Output $$$\sum\limits_{B\subseteq A} f(B)$$$ modulo $$$10^9+7$$$.
3 2 -1 2 4
10
3 1 1 1 1
7
10 4 -24 -41 9 -154 -56 14 18 53 -7 120
225905161
15 5 0 0 2 -2 2 -2 3 -3 -3 4 5 -4 -4 4 5
18119684
Consider the first sample. From the definitions we know that
So we should print $$$(0+0+0+0-2-4+8+8)\bmod (10^9+7)=10$$$.
In the second example, note that although the multiset consists of three same values, it still has $$$8$$$ distinct subsets: $$$\varnothing,\{1\},\{1\},\{1\},\{1,1\},\{1,1\},\{1,1\},\{1,1,1\}$$$.
Name |
---|