#P1220. 斐波卡契的兔子

斐波卡契的兔子

No testdata at current.

[AHOI2006]斐波卡契的兔子

题目描述

卡卡开始养兔子了!妈妈给他买了一对刚出生的兔子,卡卡了解到兔子的繁殖规律是这样的:才出生的一对兔子在一个月后将第一次生出一胎 aa 对兔子,接着在出生后的二个月又将生出 bb 对兔子,在第三个月和以后每个月都会繁殖 cc 对兔子(abca \le b \le c)。 由斐波纳契数列我们知道兔子的繁殖速度是很快的,然而卡卡有兔子一样多的好朋友,卡卡想在 mm 个月后有 kk 对兔子,以便分给他们的好友,他的愿望是否能够实现呢?

[任务] 编写一个程序:从输入文件中读入输入信息;计算 mm 个月后卡卡将有多少对兔子,设之为 PP;计算如果 mm 个月后卡卡要拥有至少 kk 对兔子,那么开始时妈妈至少应该为卡卡购买多少对兔子,设之为 QQ ;将结果输出至输出文件。

输入格式

输入文件的第一行有四个正整数:aabbccmm;而第二行则仅含一个正整数 kk。它们的含义见上文描述。

输出格式

输出两行,第一行是一个整数 PP 而第二行是一个整数 QQ

样例 #1

样例输入 #1

0 1 1 10
10000

样例输出 #1

89
113

提示

0abc1000 \le a \le b \le c \le 1001m30001 \le m \le 30001k1060001 \le k \le 10^{6000}