1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <cstdio>
typedef long long LL;
const LL P = 1000000007;
const int maxn = 1005;
int N, L, m;
LL a[maxn], C[maxn], B[maxn], T[maxn], b, d, lamb;
LL ksm(LL a, LL b, LL c) {
    LL r = 1, t = a;
    while (b) {
        if (b & 1ll) r = (r * t) % c;
        t = (t * t) % c;
        b >>= 1ll;
    }
    return r;
}
int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) scanf("%d", a + i);
    C[0] = B[0] = 1;
    b = m = 1;
    for (int i = 0; i < N; ++i) {
        d = 0;
        for (int j = 0; j <= i; ++j)
            (d += C[j] * a[i-j]) %= P;
        if (d == 0) ++m;
        else if (L * 2 <= i) {
            for (int j = 0; j < N; ++j) T[j] = C[j];
            lamb = d * ksm(b, P - 2, P) % P;
            for (int j = m; j < N; ++j) C[j] = (C[j] - lamb * B[j - m] % P + P) % P;
            L = i + 1 - L;
            for (int j = 0; j < N; ++j) B[j] = T[j];
            b = d;
            m = 1;
        }
        else {
            lamb = d * ksm(b, P - 2, P) % P;
            for (int j = m; j < N; ++j) C[j] = (C[j] - lamb * B[j - m] % P + P) % P;
            ++m;
        }
    }
    printf("%d\n", L);
    for (int i = 1; i <= L; ++i) printf("%lld ", (P - C[i]) % P);
}