The weight of a positive integer is the sum of its digits. For example, weight(12097) = 1+2+0+9+7 = 19. For any positive integer x, f(x) = 1 if weight(x) = x, and f(x) = f(weight(x))+1 otherwise. For example, f(2) = 1 and f(654) = f(15)+1 = f(6)+1+1 = 3.
Find the smallest number x that f(x) = n. The answer may be huge, just output the remainder after divided by 100007.
There are several test cases in the input.
Each test case begin with an integer n (1 <= n <= 1000000000).
The input terminates by end of file marker.
For each test case, output the result in a single line.