ZZY 的宠物

<div class="page"> <div class="layoutArea"> <div class="column"> <p> ZZY 领养了一对刚刚出生的不知名小宠物..巨萌巨可爱!!...小宠物的生命为 5 items单位时间并 且不会在中间出意外翘辫子(如: 从 0 出生能活到 5 但活不到 6)..小宠物经过 2 items单位时间成 熟..刚刚成熟的一对小宠物能立即生育 6 只新的小宠物(如: 从 0 出生的一对在 2 时成熟并进 行Page 一次生育)...小宠物是很忠诚的..不会在中途换伴侣..每对小宠物生育一次这一对的生育 能力就会降低 2 items..也就是说一对小宠物在Page 二次生育时就只能生 4 items了..小宠物成熟后每items 单位时间都会尽力的生育(例: 从0出生的一对..2时间生6items..3时间生4items..4时间生2items...5 时间生不出..6 时间这一对已经挂了..)..生育出来的新小宠物会继续这items过程.. </p> <p> ZZY 想知problems从单位时间 0 开始..经过 M items单位时间(时间为 M 时)将有多少只活着的小宠物(0 时刻有 2 只小宠物)<br /> 因为 ZZY 隐隐地觉得什么地方怪怪的...所以请将这items数目 mod 10000&nbsp; </p> </div> </div> </div>

<div class="page"> <p> <p> <p> 多组数据读到 EOF&nbsp; </p> <p> 每组数据一行:<br /> M ( 0&lt;=M&lt;=2000000000 )&nbsp; </p> <p> 最多 500 组数据&nbsp; </p> </p> </p> </div>

<div class="page"> <div class="layoutArea"> <div class="column"> <p> 每组输出一行为 Case 组号: 答案,即 M 时刻活着的小宠物items数%10000&nbsp; </p> </div> </div> </div>