众所周知，一个硬币有两面，一面朝上，一面朝下。如果两个硬币同时朝上，或者同时朝下，我们说两个硬币的状态是相同的。如果现在有N个硬币排成一排，显然有2^N种不同的排法。如果存在超过两个连续硬币的状态相同，我们就说这个硬币序列是幸运的。那么这种幸运的硬币序列有多少种呢？

第一行一个整数N。（1<=N<=10^9）表示硬币个数。

一个整数，表示幸运硬币序列的种数，数值可能会非常大，将结果Mod 10007。