Magic sequence

All submissions for this problem are available.
Johnny has invented a magic sequence. Each element of the sequence is defined by the same recursive definition  take some linear combination of previous elements (whose coefficients are fixed) and add to them the nth powers of some integers. Formally: X_{n} = X_{n1}*a_{1} + ... + X_{ni}*a_{i} + b_{1}*d_{1}^{n} + ... + b_{j}*d_{j}^{n}, for some integer constants p,q,a_{1},...,ap,b_{1},..., b_{q},d_{1},..., d_{q}. Of course, as the values can quickly grow, he computed them modulo a fixed value: 10^{6}. He wrote many consecutive values of the sequence, but then he lost most of his work. All he has now, is 10 consecutive values taken from somewhere in the sequence (he doesn't know at what n they begin), and the recursive rule. And he would like to recover the sequence, or at the very least, to be able to write the next 10 values taken from the sequence.
Input
First, two integers, 0≤p≤4, 0≤q≤4. Then come the descriptions of the coefficients, 100 ≤ a_{1},...,ap,b_{1},..., b_{q},d_{1},..., d_{q} ≤ 100. Then, the following 10 integers are X_{n},X_{n+1},...,X_{n+9} for some unknown n.
Output
Output 10 integers  X_{n+10},X_{n+11},...,X_{n+19}
Example
Input:
1 1
1
1
1
11 12 13 14 15 16 17 18 19 20
Output:
21 22 23 24 25 26 27 28 29 30
Explanation:
x_{n}=x_{n1}+1
Input:
1 1
1
1
2
1 3 7 15 31 63 127 255 511 1023
Output:
2047 4095 8191 16383 32767 65535 131071 262143 524287 48575
Explanation:
x_{n}=x_{n1}+2^{n}=...=2^{n}+2^{n1}+...+1=2^{n+1}1
Input:
2 0
1 1
1 1 2 3 5 8 13 21 34 55
Output:
89 144 233 377 610 987 1597 2584 4181 6765
Explanation:
x_{n}=Fib(n) is the nth Fibonacci number
Input:
2 1
2 1
2
1
0 1 4 9 16 25 36 49 64 81
Output:
100 121 144 169 196 225 256 289 324 361
Explanation:
x_{n}=n^{2}
Author:  admin 
Tags  admin 
Date Added:  10072009 
Time Limit:  0.156977 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, COB, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, kotlin, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, rust, SCALA, SCM chicken, SCM guile, SCM qobi, ST, swift, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 