背景

方块鸟打算把地面翻修一下，重新铺地砖。

描述

经过一轮筛选以后，小方小块小鸟选好了一种$1*2$的瓷砖，和一种拐弯的瓷砖，如下图所示：

像这个题目里一样，他们也想知道2*N的走廊有多少种不同的铺贴方式。

比如，说一个2*3的走廊，就一共有5种不同的瓷砖铺贴方式：

由于这个结果会很大，你只需要输出这个结果除以 $100,007$ 的余数即可。

输入输出格式

输入

一行，一个正整数$N$，为走廊的长度。

输出

一行，一个正整数，表示2*N的走廊有多少种不同的铺贴方式。

输入输出样例

3

5