SP12125 FIBOSQRT - Fibonacci With a Square Root
Description
FIBONACCI is the recursive sequence that is given by: F(n)=F(n-1)+F(n-2) with F(0)=0 and F(1)=1
In this problem we define FIBOSQRT that is given by: Fs(n)=Fs(n-1)+Fs(n-2)+2\*SQRT(3+Fs(n-1)\*Fs(n-2)) with Fs(0) and Fs(1) are given in the input file.
It's guaranteed that SQRT(3+Fs(n-1)\*Fs(n-2)) is always an integer.  I've proved it by math theorem.
Now your task is to find Fs(n)
Since the number can be Big you have to find the result mod M.
Input Format
The first line is an integer T(1 T
For each test case, there are four integers **Fs(0)**,**Fs(1)**(1 M(1 M < 10 $ ^{9} $ ), and **n**(0 n < 10 $ ^{18} $ ) written in one line, separated by space.
Output Format
For each test case, output Fs(**n**) mod **M**.