## Problem Description

rxw is a tutor for a junior high school student.
One day, rxw is asked a simple question:
You should select N integers arbitrarily from 1、2、3、4、5 and the number can be selected repeatly. The selected N integers format a N –digit number. We want to know there are how many N-digit numbers that mod 3 equals 1.
Rxw can not find the answer, and he turns to oaiei for help. Of course oaiei would not tell him the anwer. Can you help him?
## Input

There are multiple test cases. For each test case, there is an integer N, denoting you should select N integers from 1-5 and format a N-digit number. (1<=N<=10^6).
## Output

For each test case, you should output there are how many N-digit numbers that mod 3 equals 1 and print the answer modulo 100007 on a separate line.
## Sample Input

4

## Sample Output

208

## Source

FZU 2008 Summer Training II--Combinatorics