Description

定义一个序列 $\{a\}_{i=1}^n$ 的整齐度为：将 $\{a\}_{i=1}^n$ 随意打乱顺序，得到序列 $\{b\}_{i=1}^n$，统计满足 $a_i=b_i$ 的 $i$ 的个数，在所有的打乱方式中，$i$ 的个数的最小值。

定义一个序列的子序列（即子列），为从原数列中删去任意数（可以不删），其它数保留原来的相对顺序，得到的序列。例如，$\{1,2,4\}$ 为 $\{1,2,3,4\}$ 的子序列，但 $\{1,3,2\}$ 不是。

在本题中，两个子序列不同，当且仅当从原序列删去的数的个数不同，或者删去的数的下标的集合不同。例如，$1,2,2$ 中存在两个形如 $1,2$ 的子序列。

给定序列 $\{a\}_{i=1}^n$，对于每一个非负整数 $k\,(0\leq k\leq n)$，求 $\{a\}$ 的整齐度为 $k$ 的非空子序列个数。

答案可能很大，你只需要求出其对质数 $10^6+3$ 取模的结果即可。

Format

Input

第一行一个正整数 $n\,(1\leq n\leq 10^6)$.

第二行 $n$ 个正整数，第 $i$ 个正整数为 $a_i\,(1\leq a_i\leq n)$.

Output

输出 $n+1$ 行，每行一个数。第 $k$ 行为整齐度为 $k-1$ 的子序列个数，对 $10^6+3$ 取模。

Samples

3
1 2 2

2
4
1
0

Limitation

2s, 256MiB.

对于 $50\%$ 的数据，$1\leq n\leq 10^3$.

对于所有数据，$1\leq n\leq 10^6$.

Hint

$p$ 为质数时：

• $(a+b)\bmod p = (a\bmod p + b\bmod p)\bmod p$.
• $(-b)\bmod p = (p-b)\bmod p$.
• $(ab)\bmod p = (a\bmod p \cdot b\bmod p)\bmod p$.
• $\frac{a}{b}\bmod p = (a\cdot b^{p-2})\bmod p$.（费马小定理）

请注意，直接使用 pow,fractorial 等函数会导致数字过大而丢失数据精度，请手动用循环的方式实现。或使用快速幂的形式实现。快速幂教程：Click me.