思路:期望dp

记状态: $(i)$ 代表当前有 $i$ 个偶数, $n - i$ 个奇数.

转移:

在 $(i)$ 下，有 $\frac{n - i}{n}$ 的概率转移到 $(i + 1)$

即 $P(state = i| state = i + 1) = \frac{n-i}{n} = p$

题目内容

有 $n$ 个桶，每个桶里有一定数量的球。初始时第 $i$ 个桶中有 $b_i$ 个球。每次操作会等概率地随机选择一个桶，并向其中放入一个球。当某一时刻所有桶中的球数均为偶数时，过程停止。求停止时所有桶中球的总数的期望值。

球的总数可能很大，请输出期望值对 $10^9+7$ 取模的结果。

约束： $n$ 满足 $1 \le n \le 10^5$ ，每个 $b_i$ 满足 $0 \le b_i \le 10^9$ 。

第一行包含一个整数 $n$ ，表示桶的数量。