有 n 个格子从左到右依次排成一排，你要用红、绿、蓝三种颜色的燃料给这 n 个格子染色。要求同时满足如下两个条件：

① 每个格子必须染成红色、绿色、蓝色三种颜色中的一种；
② 不能存在连续的三个格子染成相同的颜色。

问：有多少种不同的染色方案？由于答案可能很大，你只需要输出方案数模 10007 的结果即可。

输入共一行，包含一个整数 n，表示格子个数（1 ≤ n ≤ 100,000）。

输出一个整数，表示满足题目要求的方案数模 10007 的结果。

样例解释：
一共有 24 种不同的染色方案，对应如下：
· 红 红 绿
· 红 红 蓝
· 红 绿 红
· 红 绿 绿
· 红 绿 蓝
· 红 蓝 红
· 红 蓝 绿
· 红 蓝 蓝
· 绿 红 红
· 绿 红 绿
· 绿 红 蓝
· 绿 绿 红
· 绿 绿 蓝
· 绿 蓝 红
· 绿 蓝 绿
· 绿 蓝 蓝
· 蓝 红 红
· 蓝 红 绿
· 蓝 红 蓝
· 蓝 绿 红
· 蓝 绿 绿
· 蓝 绿 蓝
· 蓝 蓝 红
· 蓝 蓝 绿

数据规模与约定：
· 对于 30% 的数据，n ≤ 100
· 对于 60% 的数据，n ≤ 1,000
· 对于 100% 的数据，1 ≤ n ≤ 100,000