## FIBOFUN - Fun with Fibonacci Series

no tags

Fibonacci series is a series in which every element is sum of previous 2 elements.

first 2elements are 0,1 and the series goes like 0,1,1,2,3,5,8,13 ........

What if you were given 2 random numbers as the starting of the series and u follow the same rule as the fibonacci rule.

for eg. if you were given 2 and 2 .. the series would become

2 2 4 6 10 16 26 .........

Now ur task is Simple ...

You will be given 2 numbers a & b .. the first and second term of the series..

you need to calculate the sum of first n numbers of the series so formed..

Since the numbers can be big you need to print the result mod some number 'M' provided in the input.

### Input

first line will have single number 't' - number of test cases.

each test case will have 4 numbers a,b,n & M

a- first number of the series

b- second number of the series

n- calculate the sum till n numbers

M- print the result mod M

### Output

single number for each case - sum of n terms mod M

### Example

```Input:
22 2 10 211 3 10 21 Output:
134Explanation - for first case series is 2 2 4 6 10 16 26 42 68 110 .. Sum is 286.. o/p = 286%21 = 13```
`NOTE -Number of test cases <=100.0 <= a,b,m <= 10^8`
`1 <= n <= 10^8`
actually n ranges from 1 to 10^8
```
```

## Code Examples

### #1 Code Example with Python Programming

```Code - Python Programming```

``````A, B, N, M = 0, 0, 0, 0

class matrix:
a = []

def __init__(self, default=None):
if default is not None:
self.a = default
else:
self.a = [[0, 0], [0, 0]]

def __mul__(self, other):
s = matrix()
for i in range(2):
for j in range(2):
for k in range(2):
s.a[i][j] += self.a[i][k] * other.a[k][j]
for i in range(2):
for j in range(2):
s.a[i][j] %= M
return s

def __pow__(self, power, modulo=None):
if power == 1:
return matrix([[1, 1], [1, 0]])
if power % 2 == 1:
return self * (self.__pow__(power - 1))
half = self.__pow__(power // 2)
return half * half

T = int(input())
for _ in range(T):
A, B, N, M = map(int, input().split())
mat = matrix([[1, 1], [1, 0]]) ** N
print((mat.a[0][0] * B + mat.a[0][1] * A - B + M) % M)``````
Copy The Code &

Input

cmd
2
2 2 10 21
1 3 10 21

Output

cmd
13
4