1077 兔兔那么可爱怎么可以吃兔兔？ - ZJOJ

1077: 兔兔那么可爱怎么可以吃兔兔？

时间限制：1.000s

内存限制：256MB

提交通过: 276 提交: 937 统计

题目描述

一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？

我们不妨拿新出生的一对小兔子分析一下：

第一个月小兔子没有繁殖能力，所以还是一对

两个月后，生下一对小兔对数共有两对

三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对

－－－－－－

依次类推可以列出下表：

经过月数	1	2	3	4	5	6	7	8	9	10	11	12	...
幼崽对数	1	0	1	1	2	3	5	8	13	21	34	55	...
成兔对数	0	1	1	2	3	5	8	13	21	34	55	89	...
总体对数	1	1	2	3	5	8	13	21	34	55	89	144	...

现在我们想知道，经过 n 月后的总体对数 Fn 。

输入格式

输入包含一个整数 n。

输出格式

输出一行，包含一个整数，表示 Fn 除以 10007 的余数。

样例输入

样例输出

分类

提交