1187 - SCU-G

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 167

Solved: 51

Description
A three tower of honoi contains 3*N disks of different sizes,
three of each size. (three of size 1, three of size 2, ... ,three of size N)
We are required to move only one disk at a time ,
without putting a larger one over a smaller one .
How many moves does it take to transfer a three tower from one
peg to another, if we are required to reproduce the original
top-to-bottom order of all the equal-size disks in the final
arrangement.
Input
The first line of the input is the number of test cases.
For each case there is only one line contains only one integer N.
Output
For each test case output the answer on a line:
how many moves does it takes mod 20080913.
sample input
6
1
4
7
11
133
1000000000
sample output
5
89
761
12281
2603941
13645968
hint
source
SCUPC
© 2015 HUST ACMICPC TEAM. All Right Reserved.