题目描述

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

【任务】编写一个程序：

1. 从输入文件中读入输入信息；
2. 计算 $m$ 个月后卡卡将有多少对兔子，设之为 $P$；
3. 计算如果 $m$ 个月后卡卡要拥有至少 $k$ 对兔子，那么开始时妈妈至少应该为卡卡购买多少对兔子，设之为 $Q$；
4. 将结果输出至输出文件。

输入格式

输入文件的第一行有 $4$ 个正整数：$a,b,c,m$；

而第二行则仅含一个正整数 $k$。它们的含义见上文描述。

输出格式

你的程序将向输出文件输出两行，第一行是一个整数 $P$ 而第二行是一个整数 $Q$。

0 1 1 10
10000

89
113

提示

$0 \leq a \leq b \leq c \leq 100, \ 1 \leq m \leq 3000, \ 1 \leq k \leq 10^{6000}$