Recurrence Solver (Traditional)A linear homogeneous recurrence relation of order d with constant coefficients has the seed values t0, t1, ... td-1 with further terms defined according to tn = c1 tn-1 + c2 tn-2 + ... + cd tn-d. For example, let d = 2. This means that the first two terms t0 and t1 have specified values. Let c1 = c2 = 1, then all terms tn for n > 1 are defined as tn = tn-1 + tn-2. When t0 = 0 and t1 = 1, the sequence begins 0, 1, 1, 2, 3, 5, 8, ... : the Fibonacci sequence.
Given the values of d, t0 ... td-1, and c1 ... cd and a non-negative integer n, can you determine the term tn in this sequence, modulo 10007?
The first line of input contains two integers separated by a space, d (0 < d ≤ 50) and n (0 ≤ n < 109).
Each of the following d lines contains one integer ti (-10000 < ti < 10000). They are given in the order t0, t1, ... td-1.
Each of the following d lines contains one integer ci (-10000 < ci < 10000). They are given in the order c1, c2, ... cd.
Output a single line containing tn modulo 10007.
Note that although the mod operator in your language may give negative results, the answer should be a non-negative integer.
This sequence is defined according to t0 = 2, t1 = 1, and tn = tn-1 + tn-2 where n > 1. This is the sequence of so-called Lucas numbers, beginning 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123. (This question was also used in the PEG short questions homework packages.)
Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Oct 19, 2008
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3