提示: 欢迎访问OurACM平台。
Problem 1683 纪念SlingShot

Accept: 681    Submit: 2364
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

已知 F(n)=3 * F(n-1)+2 * F(n-2)+7 * F(n-3),n>=3,其中F(0)=1,F(1)=3,F(2)=5,对于给定的每个n,输出F(0)+ F(1)+ …… + F(n) mod 2009。

Input

第一行是一整数m,代表总共有m个cases。

Output

对于每个case,输出一行。格式见样例,冒号后有一个空格。

Sample Input

2 3 6

Sample Output

Case 1: 37 Case 2: 313

Source

FOJ月赛-2009年2月- Coral

Submit  Back  Status  Discuss