解题思路

本题要求用给定的木棍拼出一个正多边形的方案数。根据正多边形的定义，每个正多边形的边数 $k$ 必须满足所有边的长度相等，因此需要统计每个长度出现的次数，并计算对于每个 $k$ 能够组成正 $k$ 边形的方案数。方案数等于所有长度中出现次数 $c \geq k$ 的组合数 $C(c, k)$ 之和。

解题步骤

1. 统计频率：使用哈希表统计每个长度出现的次数。
2. 预处理阶乘和逆元：为了快速计算组合数 $C(n, k)$，预处理阶乘数组 fact 和其逆元数组 inv_fact。

题目内容

Zeeman 有 $3≦n≦5×10^3$ 根木棍，其中第 $i$ 根木棍的长度为 $1≦a_i≦ 10^9$ 。

Zeeman 想知道，用这些木棍(不可合并与分割)拼出一个正多边形有多少种方案。

由于答案可能很大，请将答案对 $998$ $244$ $353$ 取模后输出。

正多边形：正多边形是由至少 $3$ 条边构成并且所有边长度均相等所有内角均相等组成的多边形。

输入描述

第一行输入一个正整数 $3≤n≤5×10^3$ ，表示木棍的数量。

第二行输入 $n$ 个正整数，其中第 $i$ 个正整数 $1≤ a_i≤10^9$ 表示第 $i$ 根木棍的长度。

输出描述

输出一行 $n-2$ 个整数，其中第 $1≦i≦ n-2$ 个整数表示拼出正 $i+ 2$ 边形的方案数对 $998$ $244$ $353$ 取模后的结果。

样例1

输入

8
1 2 1 1 3 2 2 2

输出

5 1 0 0 0 0