问题 D: 秋雨绵绵

问题 D: 秋雨绵绵

时间限制: 3 Sec  内存限制: 128 MB
提交: 29  解决: 14
[提交][状态][讨论版][命题人:]

题目描述

某年月日,林虎牛无意间坠落山崖,发现一处洞天福地。他惊奇万分,向内探索着,希望可以找到一本绝世神功的秘籍,从而称霸武林。功夫不负有心人,林虎牛在犄角旮旯里发现一本残破的书,定睛一看,竟然是天下武学出龙泉的龙泉寺不传之宝——《近世代数》!他翻开第一页,只见书上写着“欲练神功,必先自宫”。林虎牛不以为然,继续向后翻,发现了一句话“不欲自宫,须破迷踪”。然后一幅巨大的公式展现在他的面前。望着巨大的公式,林虎牛不禁感叹道:

我喜欢下雨天,喜欢听雨滴轻敲窗户的声音。我还喜欢数学,数学是世界上最优美的语言,现在定义一个数列,f(n) = b0*f(n-1) + b1*f(n-2) + c  (n ≥ 2)。

求f(n)和S,是不是超级简单啊?

你能帮助林虎牛,摆脱《近世代数》第一页命运的桎梏吗?

输入

第一行一个整数 T (1 ≤ T ≤ 10000),表示数据组数。

每组数据一行 个整数 f(0),f(1), b0,b1, c, n, M

(0 ≤ f(0), f(1), b0, b1,c,n ≤ 109,0 ≤ M ≤ 1018)

输出

对于每组数据,输出3行表示答案。

第1行,Case #n:

第2行,f(n)

第3行,S

样例输入

4
1 1 1 1 3 3 1000007
7306 706 3212 7370 272 5530 5463632982528872
8301 6758 4216 6812 5221 1263 3364759590556141
5361 6799 8850 8489 3314 4023 92841679252408

样例输出

case #1:
9
45
case #2:
209299065202560
1063977121315696
case #3:
38201780978456
512816412033891
case #4:
66715290041187
70899807864777
[提交][状态]