SP2421 ININT - Incrementing The Integer

Starting from the number '1', every time you can choose a digit from the current number and add it to the number itself. 23, for example, could be changed into 25 or 26. To get 100, using the above scheme, paths A and B are both possible. A requires 21 steps, but B needs only 17 (which is also the minimum) A. 1-2-4-8-16-17-18-19-20-22-24-28-36-39-48-56-62-68-76-83-91-100 B. 1-2-4-8-16-17-24-28-36-39-48-56-62-68-76-83-91-100 C is another 17 step solution for 100. C. 1-2-4-8-16-22-24-28-36-39-48-56-62-68-76-83-91-100 Now, you are given several numbers, for each number, print the minimum steps S and number of solutions T. As T could be quite large, you should print T%1000000007 instead.

Each line of input contains a integer K as a test case. Input ends with End Of File.

For each test case print the minimum steps and solutions in a single line. If it's impossible to get the number, print "IMPOSSIBLE" instead. ( without the quotes ).