提示: 欢迎访问OurACM平台。
Problem 1647 rxw's problem

Accept: 79    Submit: 116
Time Limit: 1000 mSec    Memory Limit : 32768 KB

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

Submit  Back  Status  Discuss