Contest Duration: - (local time) (100 minutes) Back to Home
E - Count Arithmetic Subsequences /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 制約

• 1 \leq N \leq 80
• 1 \leq A_i \leq 10^9
• 入力はすべて整数

### 入力

N
A_1 A_2 \dots A_N


### 出力

k=1,2,\dots,N に対する答えを、この順に空白区切りで一行で出力せよ。

### 入力例 1

5
1 2 3 2 3


### 出力例 1

5 10 3 0 0

• 長さ 1 の部分列は全部で 5 個あり、これらはすべて長さ 1 の等差数列です。
• 長さ 2 の部分列は全部で 10 個あり、これらはすべて長さ 2 の等差数列です。
• 長さ 3 の部分列であって等差数列であるものは、(A_1,A_2,A_3),(A_1,A_2,A_5),(A_1,A_4,A_5)3 つです。
• 長さ 4 以上の部分列であって等差数列であるものは存在しません。

### 入力例 2

4
1 2 3 4


### 出力例 2

4 6 2 1


### 入力例 3

1
100


### 出力例 3

1


Score : 475 points

### Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N. For each k = 1, 2, \dots, N, find the number, modulo 998244353, of (not necessarily contiguous) subsequences of A of length k that are arithmetic sequences. Two subsequences are distinguished if they are taken from different positions, even if they are equal as sequences.

What is a subsequence? A subsequence of a sequence A is a sequence obtained by deleting zero or more elements from A and arranging the remaining elements without changing the order.

### Constraints

• 1 \leq N \leq 80
• 1 \leq A_i \leq 10^9
• All input values are integers.

### Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N


### Output

Print the answers for k = 1, 2, \dots, N in this order, in a single line, separated by spaces.

### Sample Input 1

5
1 2 3 2 3


### Sample Output 1

5 10 3 0 0

• There are 5 subsequences of length 1, all of which are arithmetic sequences.
• There are 10 subsequences of length 2, all of which are arithmetic sequences.
• There are 3 subsequences of length 3 that are arithmetic sequences: (A_1, A_2, A_3), (A_1, A_2, A_5), and (A_1, A_4, A_5).
• There are no arithmetic subsequences of length 4 or more.

### Sample Input 2

4
1 2 3 4


### Sample Output 2

4 6 2 1


### Sample Input 3

1
100


### Sample Output 3

1