该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

       朱老师对现在一个月0.3w的工资很不满意，于是准备外出兼职去搬砖。朱老师到达工厂，包工头对朱老师说：你面前有两块类型的板砖A和B，假设这些砖有无限块。我需要你搬n块搬砖到指定地点。（不能多也不能少）但是如果想要搬B类型的砖，就必须要搬两块。

       麻烦你帮小朱老师算一下，小朱老师有多少种办法可以将n块板砖搬到指定地点。

输入

第一行包含一个正整数n，表示有n块板砖。

输出

有多少种办法可以将n块板砖搬到指定地点。这个数可能很大，结果对100007取模。

Samples

2

2

样例解释： AA BB一共两种

数据范围

对于40％的数据１＜＝ｎ＜＝１0．

对于１00％的数据　１＜＝ｎ＜＝3000，