2512: 蒜头君的兔子
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
蒜头君的小伙伴在 第一年 送给他一对 一岁 的兔子，并告诉他：这种兔子 刚生下来时算 0 岁，到了 2 岁时就可以繁殖了，它在 2−10 岁时，每年会生下来一对兔子，这些兔子到了 2 岁也可以繁殖，但这些兔子在 10 岁那年 生完仔后 不久就会死亡，蒜头君想知道，第 n 年兔子 产仔之后（第 n 年 10 岁的兔子此时已经死亡），他会有多少对兔子。结果对 1000000007 取模。
Input
共一行，一个正整数 n，表示蒜头君想知道第 n 年的兔子总对数。
Output
输出一个整数，表示第 n 年兔子总对数对 1000000007 取模的值。
Sample Input Copy
样例输入1
10
样例输入2
88
样例输入3
10086Sample Output Copy
样例输出1
88
样例输出2
352138150
样例输出3
405567313
HINT
对于 30% 的数据，满足 1≤n≤103；
对于 60% 的数据，满足 1≤n≤105；
对于 100% 的数据，满足 1≤n≤109。