题目描述

斐波那契养的兔子全世界都很有名，因为他的兔子有个很奇怪的特性：从生下来的第三天开始每天早上都会生一个小兔子。

为了赚钱养家糊口，某天斐波那契带着1个刚生下的兔子开了个动物园（当然只有兔子）。由于没钱打广告，这一天只来了一个游客。这个游客看到传说中斐波那契的兔子后大为惊讶，于是第二天他又带着一个朋友来了。此后的每一天，每一个来过动物园的游客都会带着一个没来过的朋友来参观。由于随着兔子越来越多，养护费用也会越来越高，所以斐波那契决定每一天的门票价钱就等于这一天动物园内的兔子数目（动物园都是在早晨兔子生完仔以后才开门的）。
某一天，斐波那契想知道自己赚了多少钱(就是指门票的总收入，不计其他成本开支)，你能告诉他吗？

输入要求

第一行一个整数T(T<60)，表示有几组数据。
每组数据包含一个整数N(0 < N < 10^9)，表示斐波那契询问他在第N天赚了多少钱。

输出要求

对应每组数据输出例子序号以及结果，具体格式见Sample Output。
最终结果可能会很大，对1000000007(10^9+7)取模。

输入样例

6
1
2
3
4
5
1000000000

输出样例

Case 1: 1
Case 2: 3
Case 3: 11
Case 4: 35
Case 5: 115
Case 6: 15625000

提示

第一天只有一只兔子，因此门票价格为1。因为游客也只有一个，所以当天门票收入为1*1=1。

来源

The 9th NBU Programming Contest