#2036. 聪明的阿卑多

内存限制:64 MiB 时间限制:5 Sec

题目描述

也许你从没听说过阿卑多,但你一定知道他爷爷的爷爷的爷爷,那就是聪明绝顶的阿凡提先生。是的,阿卑多也是个聪明的小孩。 一天,阿卑多骑着他的小毛驴,在小镇上晃悠,正好遇上了小巴依——那个自以为是的小财主。小巴依正在炫耀他的金币: “你们见过这样的金币么?这可不是一般的金币,你看它们多大多重啊!最主要的是,它们每个上面都刻有我的名字和一个编号,是独一无二的!看看,从我出生开始,每2个月,爸爸便给我1个特做的大金币,并从1开始编号,现在我已经有60枚了,哈哈……” 小巴依见了阿卑多,于是便想考一考他:“阿卑多,听说你是最聪明的。看见我每个金币上的数字了吗?你现在拿取一半的金币,并能用你拿的若干金币上的数的和表示我的任意一枚金币上的数。如果你能办到,那么就奖你一枚金币;如果不能,就给我做三年长工好了。” 阿卑多想了一想,说:“我可以只拿1/10就办到,不过如果我办到了,你就得分一半金币给我。” 1/10?小巴依心想,你准备给我当长工好了。 于是阿卑多开始取金币…… 自然,阿卑多出色的完成了任务,得到了30枚金币,同样的,他把这些金币都分给了穷人们。 给你的任务就不同了。

输入格式

一个数n(1<=n<=1000)表示金币枚数(金币上的数分别为1到n)

输出格式

两个数,阿卑多最少要拿的金币数以及不同的方案数。

样例

样例输入


			
6

样例输出


			
3 2
(2种拿法:拿取编号为1、2、3的金币;或拿取编号为1、2、4的金币)

数据范围与提示