Tianjin University Online Judge
Contests Virtual Contests Problems Submit Runs Status Rank List Forum

2218.   Super Square
Time Limit: 1.0 Seconds   Memory Limit: 65536K
Total Runs: 5763   Accepted Runs: 1631



If N Ns are added together, we know that it's the square of N. Well, if N Ns are multiplied together, we call it a super square of N. For example, the square of 3 is 3+3+3=9, while the super square is 3*3*3=27. It is quite easy for you, a clever programming fan, to calculate the super square of integers. Am I right?

Input

The input consists of several lines, each line contains an integer N (0 < N < 108). Input is terminated by N=0.

Output

For each test case, print a line with a single integer, which is the remainder of N's super square divides 2006 (the N's super square MOD 2006).

Sample Input

2
3
4
0

Sample Input

4
27
256 



Source: TOJ 2006 Weekly Contest 5
Submit   List    Runs   Forum   Statistics

Tianjin University Online Judge v1.3.0
Maintance:Fxz. Developer: SuperHacker, G.D.Retop, Fxz