题目描述

飞镖游戏虽好玩，但小老虎不忘考考同学的数学能力，为了好玩和不大难，小老虎想就用 $5$ 个阿拉伯数吧。$1、2、3、4、5$ 数字组成一个 $N$ 位的数(可以重复使用,也可以不用),有多少个数 $I$ ,满足 $I$ $mod$ $3=1$。

输入格式

$1$ 个整数 $N$。

数据规模

对于 30% 的数据，$N \le 8$

对于 100% 的数据，$N \le 1000000$

输出格式

一个整数，即满足要求的数的个数 $mod$ $100007$。

样例

4

208