Recurrence Solver (Traditional)

A linear homogeneous recurrence relation of order d with constant coefficients has the seed values t₀, t₁, ... t_d-1 with further terms defined according to t_n = c₁ t_n-1 + c₂ t_n-2 + ... + c_d t_n-d. For example, let d = 2. This means that the first two terms t₀ and t₁ have specified values. Let c₁ = c₂ = 1, then all terms t_n for n > 1 are defined as t_n = t_n-1 + t_n-2. When t₀ = 0 and t₁ = 1, the sequence begins 0, 1, 1, 2, 3, 5, 8, ... : the Fibonacci sequence.

Given the values of d, t₀ ... t_d-1, and c₁ ... c_d and a non-negative integer n, can you determine the term t_n in this sequence, modulo 10007?

Input
The first line of input contains two integers separated by a space, d (0 < d ≤ 50) and n (0 ≤ n < 10⁹).
Each of the following d lines contains one integer t_i (-10000 < t_i < 10000). They are given in the order t₀, t₁, ... t_d-1.
Each of the following d lines contains one integer c_i (-10000 < c_i < 10000). They are given in the order c₁, c₂, ... c_d.

Output
Output a single line containing t_n modulo 10007.
Note that although the mod operator in your language may give negative results, the answer should be a non-negative integer.
Sample Input
2 10
2 1
1 1

Sample Output
123

Explanation
This sequence is defined according to t₀ = 2, t₁ = 1, and t_n = t_n-1 + t_n-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.)

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Oct 19, 2008
Author: bbi5291

Problem Types: [Show] [Hide]

• Math

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...