SumOfTerms | Topcoder Archive

Problem Statement

There is a recurrent sequence F. Its first T terms are F[i]=firstTerms[i], for i from 0 through T-1. For i >= T, F[i] is given by the following recurrence relation:

F[i] = sum (for j from 0 through T-1) coefficients[j]*F[i+j-T]

You're given two int[]s firstTerms and coefficients, containing T elements each, and one long n. Compute and return the sum of the first n terms of sequence F, modulo 1,000,000,007.

Definition

Class:: SumOfTerms
Method:: find
Parameters:: int[], int[], long
Returns:: int
Method signature:: int find(int[] firstTerms, int[] coefficients, long n)
(be sure your method is public)

Constraints

coefficients and firstTerms will each contain T elements.
T will be between 1 and 50, inclusive.
Each element of firstTerms will be between 1 and 1,000,000, inclusive.
Each element of coefficients will be between 1 and 1,000,000, inclusive.
n will be between T and 1,000,000,000,000,000,000 (10^18), inclusive.

Examples

```
{1,1}
```
```
{1,1}
```
```
10
```
```
Returns: 143
```
You have to calculate the sum of the first 10 Fibonacci numbers, which is 1+1+2+3+5+8+13+21+34+55=143.
```
{1,1,1}
```
```
{1,1,1}
```
```
6
```
```
Returns: 20
```
Here, the sum of the first 6 elements is of sequence F is 1+1+1+3+5+9=20.

{1,2,3,4,5}

{1,2,3,4,5}

Returns: 257710570

Don'f forget the modulo.

{1,1,1,1,1,1,1,1,1,1}

{1,1,1,1,1,1,1,1,1,1}

1000000000

Returns: 311096402

```
{1,2,3,4}
```
```
{1,2,3,4}
```
```
8
```
```
Returns: 3969
```
```
{1,1}
```
```
{20,14}
```
```
5
```
```
Returns: 8156
```
```
{5,2}
```
```
{7,7}
```
```
6
```
```
Returns: 25648
```

{18467,26500,15724,29358,24464,28145,16827,491,11942,5436,14604,153,12382,18716,19895,21726,11538,19912,26299,9894,23811,30333,4664,7711,6868,27644,32757,12859,9741,778,3035,1842,30106,8942,22648,23805,6729,15350,31101,3548,12623,19954}

{6334,19169,11478,26962,5705,23281,9961,2995,4827,32391,3902,292,17421,19718,5447,14771,1869,25667,17035,28703,31322,17673,15141,28253,25547,32662,20037,8723,27529,12316,22190,288,9040,19264,27446,15890,24370,15006,24393,19629,24084,18756}

66184963788291

Returns: 994804944

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.