题目内容

在城市的一角，有 $n$ 个广场，由 $n-1$ 条步行街相连，整个网络连通且没有环路（任意两个广场之间有且仅有一条路径）。每个广场上生活着一些鸽子，第 $i$ 个广场上有 $a_i$ 只鸽子。

市长计划关闭一部分步行街，使得整个网络被分割成若干个连通的区域。为了便于鸽子成对飞行，他要求每个区域内部鸽子的总数必须能被 $2$ 整除。

对于每个 $k = 1, 2, \dots, n-1$，请你计算：恰好关闭 $k$ 条步行街之后，能够使得所有区域的鸽子总数均能被 $2$ 整除的方案数。如果不存在任何方案，对应的答案为 $0$。两种方案若关闭的步行街集合不同，则视为不同的方案。

由于答案可能很大，你需要输出每个 $k$ 对应的方案数对 $10^9+7$ 取模的结果。

数据范围：广场的数量 $n$ 满足 $2 \le n \le 10^5$，每个广场上的鸽子数量 $a_i$ 满足 $1 \le a_i \le 10^9$。保证输入的步行街构成一个连通且无环的图。