logo AlgoBeat OnlineJudge
登录 注册

#102999. [BZOJ 2999] inint

内存限制:256 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

从起点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

输入格式

每行一个n。

输出格式

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

如果不能得到n,输出‘IMPOSSIBLE’。

样例

样例输入

16

100

87

样例输出

4 1

17 2


 
对于100%的数据,n