Minimum linear recurrence
Work modulo \(p=1\,000\,000\,007\). Given a sequence
\(s_0,s_1,\ldots,s_{n-1}\), find its shortest linear recurrence
\[
s_i=c_1s_{i-1}+c_2s_{i-2}+\cdots+c_ds_{i-d}
\]
that holds for every (i\ge d) in the given sequence.
Input
The first line contains (n), followed by (n) sequence values.
Output
Print the minimum order (d), followed by (c_1,c_2,\ldots,c_d). The empty
sequence recurrence has (d=0). All arithmetic is modulo (p).
Constraints
- \(1\le n\le 2000\)
- Every sequence value is an integer in \([0,p)\)