Repeated Calculations

All submissions for this problem are available.
Kaneki and Hide are bored at college, so they decide to play a small game to test how well both of them are at calculating large values. At the beginning of the game, Kaneki picks two numbers $a$ and $b$, and Hide picks two numbers $c$ and $d$. Initially, two numbers, **1000 and 7**, are written on a blackboard (these numbers will always be the first two numbers on the board). When it’s Kaneki’s turn, he calculates $ax+by$, where $x$ is the last number written on the board and $y$ is the secondlast number written on the board, and writes this value on the board. Similarly, when it’s Hide’s turn, he calculates $cx+dy$, where $x$ and $y$ have the same meanings as above, and writes this value on the board. Formally, if $f(n)$ denotes the $n^{th}$ number written on the board, initially $f(1)=1000$ and $f(2)=7$. If Kaneki is writing the $n^{th}$ number on the board, then $f(n) = a \times f(n1)+b \times f(n2)$. Else, if Hide is writing the $n^{th}$ number on the board, then $f(n) = c \times f(n1)+d \times f(n2)$. Note that when the game starts, Kaneki would be writing the $3^{rd}$ number on the board. You, a programmer, have come across these two friends playing this game, and you wonder: given $a$, $b$, $c$, $d$, what will be the $n^{th}$ number written on the board? Note that since the blackboard is of limited size, the friends have agreed to write all numbers modulo $10^9+7$. ###Input:  First line will contain $t$, number of testcases. Then the testcases follow.  Each testcase consists of a single line of input containing 5 integers $a$, $b$, $c$, $d$ and $n$. ###Output: For each testcase, in a single line, output the $n^{th}$ number written on the board modulo $10^9+7$. ###Constraints  $1 \leq t \leq 10000$  $1 \leq a, b, c, d, n \leq 10^9$ ###Sample Input: 5 1 1 2 1 1 1 1 2 1 2 1 1 2 1 3 1 1 2 1 4 1 1 2 1 5 ###Sample Output: 1000 7 1007 2021 3028 ###EXPLANATION: For all the testcases in the sample input, $a=1$, $b=1$, $c=2$ and $d=1$. For $n=1$, the answer is the first number written on the board, which, according to the question, is 1000. For $n=2$, again, according to the question, the answer is 7. For $n=3$, Kaneki calculates $ax+by$ which is $1 \times 7 + 1 \times 1000 = 1007$. For $n=4$, Hide calculates $cx+dy$ which is $2 \times 1007 + 1 \times 7 = 2021$. Finally, for $n=5$, Kaneki calculates $ax+by$ which is $1 \times 2021 + 1 \times 1007 = 3028$.Author:  teja349 
Tags  teja349 
Date Added:  9042018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions