F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Buge's Fibonacci Number Problem

Time 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
3 1 1 1 1 1 2 100000 1 1 1 1 1 3 100000 1 1 1 1 1 4 100000
 

Sample Output
2 4 7
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-12-11 19:54:18, Gzip enabled