零崎的人间冒险Ⅱ

时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 434 总提交人数: 482

题目描述

零崎本以为他的无聊冒险马上就要结束了,然而实际上距离魔王的魔法成功发动还有很久很久,于是他的无聊冒险还可以继续…… 无聊的零崎需要给自己的冒险找点事做,然而实际上他的日常非常平和,如果说有什么意外的话,那就是他去打麻将了。零崎在玩一种叫做日式麻将的竞技游戏,然而无聊的零崎总是遭遇别人立直需要防守的场面。 零崎在防守时,会跟打现物和搏筋兜牌两种技能,然而为了不被婊得太惨,零崎不会连续搏筋兜牌。也就是说,零崎任意两次选择中不会都是搏筋兜牌。 那么对于n次舍牌,无聊的零崎会有多少种选择? 因为无聊的零崎可以打很久的麻将,所以n可能很大,无聊的零崎决定只要结果对100007求模后的选择数。

输入

多组输入数据,每组一个数字n,1<=n<=Int_MAX

输出

每组一行,只需要选择种数对100007求模后的结果。

输入样例

1
2

输出样例

2
3

Hint

听说这个也是很简单的,不然你们推推递推公式看?
ps:
n=1:刚,怂
n=2 刚怂,怂怂,怂刚
n=3 刚怂怂,刚怂刚,怂怂怂,怂怂刚,怂刚怂