UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2999. inint

统计 下载数据

Description

从起点1开始,每次选择当前数的任意一位上加上去,问得到n的最小步数以及方案数。多组数据。
 
例如,从1开始得到100,有很多方法,其中有下面两种方式:
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
显然,B只需要17步。
而事实上,有两种17步的方法。
C. 1-2-4-8-16-22-24-28-36-39-48-56-62-68-76-83-91-100
 
 

Input

 
每行一个n。
 

Output

 

对于每组测试数据,输出一行两个数,表示得到n的最小步数以及方案数。方案数需要mod 1000000007。
如果不能得到n,输出‘IMPOSSIBLE’。

Sample Input

16

100

87



Sample Output


4 1

17 2



对于100%的数据,n<=10^9,数据组数不超过100。

Hint

Source