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 

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