聪明的阿卑多

也许你从未听说过阿卑多，但你一定知道他爷爷的爷爷的爷爷——聪明绝顶的阿凡提先生。阿卑多也是一个聪明的孩子。

一天，阿卑多骑着小毛驴在小镇上闲逛，正好遇到了小巴依——一个自以为是的小财主。小巴依正在炫耀他的金币：

“你们见过这样的金币吗？这可不是一般的金币，它们又大又重。最重要的是，每枚金币上都刻有我的名字和一个独一无二的编号。从我出生开始，爸爸每 $2$ 个月就会送给我 $1$ 枚特制的大金币，并从 $1$ 开始依次编号。现在我已经有 $60$ 枚了！”

小巴依见到阿卑多，便想考一考他：

“阿卑多，听说你非常聪明。你可以拿走一半的金币，但必须保证：对于我的任意一枚金币，你都能从拿走的金币中选出若干枚，使它们的编号之和等于这枚金币的编号。如果你能办到，我就奖励你一枚金币；如果不能，你就要给我做 $3$ 年长工。”

阿卑多想了想，说：“我只需要拿走全部金币的 $\frac{1}{10}$ 就能办到。不过，如果我成功了，你要把一半的金币分给我。”

小巴依并不相信，但阿卑多最终出色地完成了任务，得到了 $30$ 枚金币，并把它们全部分给了穷人。

现在，你面临一个类似的问题：共有 $n$ 枚金币，编号依次为 $1$ 到 $n$ 。你需要选取若干枚金币，使得对于每个编号，都能从选取的金币中找出若干枚，其编号之和恰好等于该编号。

请计算最少需要选取多少枚金币，以及达到这一最小数量的不同选取方案数。

输入格式

输入一个整数 $n$ ，表示金币的数量。金币的编号依次为 $1$ 到 $n$ 。

输出 $2$ 个整数，分别表示最少需要选取的金币数量，以及达到这一最小数量的不同方案数。

3 2

共有 $2$ 种最优方案：选取编号为 $1$ 、 $2$ 、 $3$ 的金币，或选取编号为 $1$ 、 $2$ 、 $4$ 的金币。

本题题面与测试数据整理自 BZOJ。

3 2