|Contests||Virtual Contests||Problems||Submit||Runs Status||Rank List||Forum|
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?
The input consists of several lines, each line contains an integer N (0 < N < 108). Input is terminated by N=0.
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).