Magic Transformation Sequence

You are given a non-negative integer array \(\{a_i\}_{i=1}^n\) of length \(n\). A magical transformation is defined as follows:

\[ f_k = \left(\sum_{i=1}^n a_i^k\right) \bmod 998244353, \quad \text{for } 1 \le k \le n \]

Your task is to compute the sequence \(f_1, f_2, \dots, f_n\) and output the results in order.

inputFormat

The first line contains an integer \(n\) which is the length of the array. The second line contains \(n\) space-separated non-negative integers \(a_1, a_2, \dots, a_n\).

outputFormat

Output \(n\) integers \(f_1, f_2, \dots, f_n\) separated by a single space, where \(f_k = \left(\sum_{i=1}^n a_i^k\right) \bmod 998244353\).

sample

3
1 2 3

6 14 36