## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Maximum Product? Codeforces Solution | Codeforces Problem Solution 2022

H. Maximum Product?
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a positive integer $k$. For a multiset of integers $S$, define $f\left(S\right)$ as the following.

• If the number of elements in $S$ is less than $k$$f\left(S\right)=0$.
• Otherwise, define $f\left(S\right)$ as the maximum product you can get by choosing exactly $k$ integers from $S$.

More formally, let $|S|$ denote the number of elements in $S$. Then,

• If $|S|$f\left(S\right)=0$.
• Otherwise, $f\left(S\right)=\underset{T\subseteq S,|T|=k}{max}\left(\prod _{i\in T}i\right)$.

You are given a multiset of integers, $A$. Compute $\sum _{B\subseteq A}f\left(B\right)$ 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

Solution Click Below:-  👉
👇👇👇👇👇

equal.

Input

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

Output $\sum _{B\subseteq A}f\left(B\right)$ modulo ${10}^{9}+7$.