|
||||||||||
Buge's Fibonacci Number ProblemTime Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 1068 Accepted Submission(s): 361 Problem Description snowingsea is having Buge¡¯s discrete mathematics lesson, Buge is now talking about the Fibonacci Number. As a bright student, snowingsea, of course, takes it as a piece of cake. He feels boring and soon comes over drowsy. Buge£¬feels unhappy about him, he knocked at snowingsea¡¯s head, says:¡±Go to solve the problem on the blackboard!¡±, snowingsea suddenly wakes up, sees the blackboard written : snowingsea thinks a moment£¬and writes down: snowingsea has a glance at Buge£¬Buge smiles without talking, he just makes a little modification on the original problem, then it becomes : The modified problem makes snowingsea nervous, and he doesn't know how to solve it. By the way£¬Buge is famous for failing students, if snowingsea cannot solve it properly£¬ Buge is very likely to fail snowingsea. But snowingsea has many ACM friends. So£¬snowingsea is asking the brilliant ACMers for help. Can you help him? Input The input consists of several test cases. The first line contains an integer T representing the number of test cases. Each test case contains 7 integers, they are f1, f2, a, b, k, n, m which were just mentioned above, where 0 < f1, f2, a, b, n, m < 1000 000 000, and 0 ¡Ü k < 50. Output For each case, you should print just one line, which contains S(n,k) %m. Sample Input
Sample Output
Source | ||||||||||
|