Given $f_1, f_2, \dots, f_n$, find the shortest linear recurrence sequence $f_n = \sum_{i=1}^k f_{n-i}c_i$ (for $n \geq k$). All calculations are performed modulo $998244353$.

Input

The first line contains an integer $n$.

The next line contains $n$ integers $f_1, f_2, \dots, f_n$.

Output

The first line contains an integer $k$.

The next line contains $k$ integers $c_1, c_2, \dots, c_k$, representing the answer.

If there are multiple valid sequences $c$, you may output any one of them.

Examples

Input 1

2
1 1

Output 1

1
1

Input 2

6
1 1 4 5 1 4

Output 2

3
781234712 737832781 130205788

Subtasks

For all test cases, $0 \le n \leq 10^4$ and $0 \le f_i < 998\,244\,353$.