#1595. ZZY 的宠物_1

ZZY 的宠物_1

说明

ZZY 领养了一对刚刚出生的不知名小宠物..巨萌巨可爱!!...小宠物的生命为 5 个单位时间并 且不会在中间出意外翘辫子(如: 从 0 出生能活到 5 但活不到 6)..小宠物经过 2 个单位时间成 熟..刚刚成熟的一对小宠物能立即生育 6 只新的小宠物(如: 从 0 出生的一对在 2 时成熟并进 行第一次生育)...小宠物是很忠诚的..不会在中途换伴侣..每对小宠物生育一次这一对的生育 能力就会降低 2 个..也就是说一对小宠物在第二次生育时就只能生 4 个了..小宠物成熟后每个 单位时间都会尽力的生育(例: 从0出生的一对..2时间生6个..3时间生4个..4时间生2个...5 时间生不出..6 时间这一对已经挂了..)..生育出来的新小宠物会继续这个过程..

ZZY 想知道从单位时间 0 开始..经过 M 个单位时间(时间为 M 时)将有多少只活着的小宠物(0 时刻有 2 只小宠物)
因为 ZZY 隐隐地觉得什么地方怪怪的...所以请将这个数目 mod 10000 

输入格式

多组数据读到 EOF 

每组数据一行:
M ( 0<=M<=2000000000 ) 

最多 500 组数据 

输出格式

每组输出一行为 Case 组号: 答案,即 M 时刻活着的小宠物个数%10000 

样例

0
1
2
3
4
8
Case 1: 2
Case 2: 2
Case 3: 8
Case 4: 12
Case 5: 32
Case 6: 528