## Recurrence Solver (Traditional)

A*linear homogeneous recurrence relation of order*d

*with constant coefficients*has the seed values

*t*

_{0},

*t*

_{1}, ...

*t*

_{d-1}with further terms defined according to

*t*

_{n}=

*c*

_{1}

*t*

_{n-1}+

*c*

_{2}

*t*

_{n-2}+ ... +

*c*

_{d}

*t*

_{n-d}. For example, let

*d*= 2. This means that the first two terms

*t*

_{0}and

*t*

_{1}have specified values. Let

*c*

_{1}=

*c*

_{2}= 1, then all terms

*t*

_{n}for

*n*> 1 are defined as

*t*

_{n}=

*t*

_{n-1}+

*t*

_{n-2}. When

*t*

_{0}= 0 and

*t*

_{1}= 1, the sequence begins 0, 1, 1, 2, 3, 5, 8, ... : the Fibonacci sequence.

Given the values of

*d*,

*t*

_{0}...

*t*

_{d-1}, and

*c*

_{1}...

*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

^{9}).

Each of the following

*d*lines contains one integer

*t*

_{i}(-10000 <

*t*

_{i}< 10000). They are given in the order

*t*

_{0},

*t*

_{1}, ...

*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*

_{1},

*c*

_{2}, ...

*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*

_{0}= 2,

*t*

_{1}= 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]

**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...