**Author:** Anuj Maheshwari

**Editorialist:** Vaibhav Jain

### DIFFICULTY:

EASY-MEDIUM

### PREREQUISITES:

Linear Recurrence Relation

### PROBLEM:

You are given two sequences A and B, each with size M, and an integer N. Consider the following pseudocode:

```
result := 0
for i := 1 to M
for j := 1 to M
array fib[1..max(2, N)]
fib[1] := A[i]
fib[2] := B[j]
for k := 3 to N
fib[k] := fib[k-1] + fib[k-2]
result := result + fib[N]
```

Compute the final value of the variable result

### EXPLANATION:

Well approach which I am providing is quite simple.

Consider sample test case:

3 n

1 2 3

4 5 6

Now, we know for n=1 nth terms for combinations (1,4), (1,5), (1,6), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6) will be 1,1,1,2,2,3,3,3 i.e. m times the total sum of first array.

Same is for n=2 where we need to sum of second array and multiply with m.

Now when n>=3

```
1+4=5
4+5=9
1+5=6
5+6=11
1+6=7
6+7=13
2+4=6
4+6=10
2+5=7
5+7=12
2+6=8
6+8=14
3+4=7
4+7=11
3+5=8
5+8=13
3+6=9
6+9=15
```

for n>=3 what we can do is take three variables s1, s2 and s3. s1 will hold sum of first array mulplied with m and s2 will hold sum of second array multiplied with m. s3 will hold sum of s1 and s2. These are initial conditions.

Now what can we see from above series is that when n=3, we need to have

(1+4)+(1+5)+(1+6)+(2+4)+(2+5)+(2+6)+(3+4)+(3+5)+(3+6)

(1+2+3)*m + (4+5+6)*m

i.e. s1+s2 which will be stored in s3

for n=4,

(4+5)+(5+6)+(6+7)+(4+6)+(5+7)+(6+8)+(4+7)+(5+8)+(6+9)

(4+5+6)*m + (5+6+7+6+7+8+7+8+9)

i.e. s2+s3

hence for n>=3

for(int i=2;i<n;i++)

{

s3=(s1+s2)%mod;

s1=s2;

s2=s3;

}

print(s3)

### TIME COMPLEXITY:

*O(n+m)* per test case