暂无测试数据。

蒜头君的小伙伴在 第一年 送给他一对 一岁 的兔子，并告诉他：这种兔子 刚生下来时算 $0$ 岁，到了 $2$ 岁时就可以繁殖了，它在 $2-10$ 岁时，每年会生下来一对兔子，这些兔子到了 $2$ 岁也可以繁殖，但这些兔子在 $10$ 岁那年 生完仔后 不久就会死亡，蒜头君想知道，第 $n$ 年兔子 产仔之后（第 $n$ 年 $10$ 岁的兔子此时已经死亡），他会有多少对兔子。结果对 $1000000007$ 取模。

输入格式

共一行，一个正整数 $n$，表示蒜头君想知道第 $n$ 年的兔子总对数。

输出格式

输出一个整数，表示第 $n$ 年兔子总对数对 $1000000007$ 取模的值。

数据规模

对于 $30$% 的数据，满足 $1 \le n \le 10^3$；

对于 $60$% 的数据，满足 $1 \le n \le 10^5$；

对于 $100$% 的数据，满足 $1 \le n \le 10^9$。

10

88

88

352138150

10086

405567313