Marble Council

Let $c_v$ be the frequency of value $v$ in the original multiset. Values with $c_v=0$ are useless, so ignore them.

We need count possible output frequency vectors $b_v$, where $b_v$ is how many times value $v$ appears in the generated multiset $s$.

Obviously,

$0\le b_v\le c_v,$

because each group that outputs $v$ must contain at least one copy of $v$.

The non-obvious part is deciding which combinations of positive $b_v$ are actually possible.

The Key Characterization

Let

$C=\max_v c_v$

be the largest original frequency.

For some candidate output, define

$P=\{v\mid b_v>0\}.$

So $P$ is the set of values that appear in the output at least once.

The claim is:

$\text{the output is possible iff } \sum_{v\in P} c_v \ge C.$

That is the whole problem. The rest is just counting.

Why This Condition Is Necessary

Look at any valid partition. Each group has a chosen mode. Suppose a group chooses value $x$, and $x$ appears $m$ times inside that group.

Then every other value can appear at most $m$ times in that group, otherwise $x$ would not be a mode.

Now add up these chosen-mode counts over all groups. Call the total $T$.

Take any value $y$. Across all groups, the copies of $y$ can never exceed this total capacity $T$: in groups choosing $y$, its own copies contribute to $T$; in groups not choosing $y$, it can appear at most as many times as the chosen mode of that group.

So every frequency satisfies

$c_y\le T.$

In particular,

$C\le T.$

But the chosen modes only come from values in $P$, so the total number of chosen-mode copies cannot exceed all copies of values in $P$:

$T\le \sum_{v\in P} c_v.$

Therefore,

$\sum_{v\in P} c_v\ge C.$

No way around it. If the biggest pile has size $C$, your selected output values need enough total mass to contain/absorb it. Math does not care about vibes.

Why This Condition Is Sufficient

Now suppose we picked some set $P$ such that

$\sum_{v\in P} c_v\ge C.$

Also suppose for each $v\in P$ we picked any positive count

$1\le b_v\le c_v.$

We will build a valid partition.

For every selected value $v\in P$, split all $c_v$ copies of $v$ among exactly $b_v$ groups, all choosing $v$ as their mode. This is always possible because $b_v\le c_v$.

Now the total chosen-mode capacity across all these groups is

$S=\sum_{v\in P} c_v.$

Every unselected value $u\notin P$ has

$c_u\le C\le S.$

So we can distribute its $c_u$ copies among the existing groups, never putting more copies into a group than that group's chosen-mode count. This keeps the chosen value tied for maximum or strictly maximum, so it remains a valid mode.

Different unselected values do not interfere with each other, because the mode condition compares each value's count separately. A group can contain many foreign values, each up to the chosen-mode count. Ties are allowed. Very convenient, almost suspiciously so.

Thus the condition is sufficient.

Counting Outputs

For each selected set $P$, how many output multisets use exactly those values?

For every $v\in P$, $b_v$ can be any number from $1$ to $c_v$, giving $c_v$ choices.

So this set contributes

$\prod_{v\in P} c_v$

if

$\sum_{v\in P} c_v\ge C.$

Therefore the answer is

$\sum_{P:\ \sum_{v\in P}c_v\ge C}\prod_{v\in P}c_v.$

Instead of summing good subsets directly, count all subsets and subtract bad ones.

All subsets weighted by $\prod c_v$ contribute:

$\prod_v(1+c_v),$

because for each value we either do not select it, contributing $1$, or select it, contributing $c_v$.

Bad subsets are those with total frequency less than $C$.

Use knapsack DP:

$dp[j]=\text{total weighted contribution of selected subsets with frequency sum }j.$

Initialize $dp[0]=1$. For each frequency $c$, update downward:

$dp[j+c] += dp[j]\cdot c.$

Only keep sums $j<C$, since those are the bad ones.

Then

$bad=\sum_{j=0}^{C-1}dp[j],$

and

$answer=\prod_v(c_v+1)-bad.$

The empty subset is included in $bad$, which is exactly what we want, since the empty output is impossible.

Complexity

For each test case, the DP size is $C\le n$, and the number of positive frequencies is at most $n$.

So the complexity is

$O(nC)\le O(n^2),$

and since the sum of $n$ over all tests is at most $5000$, this easily fits.