题目描述

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

输入数据

一个数 $n$ 表示金币枚数（金币上的数分别为 $1$ 到 $n$）。

输出数据

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

样例输入

6

样例输出

32

样例说明

$2$ 种拿法：拿取编号为 $1$、$2$、$3$ 的金币；或拿取编号为 $1$、$2$、$4$ 的金币。

数据规模与约定

对于 $100\%$ 的数据，$1 \leq n \leq 10^3$。