[SCOI2006]整数划分

给定一个正整数 $n$，要求将 $n$ 表示为若干个正整数之和，并使这些正整数的乘积最大。

例如，当 $n=13$ 时，表示为 $4+3+3+3$ 或 $2+2+3+3+3$ 时，乘积均为最大值 $108$。

输入格式

输入一个正整数 $n$。

输出格式

第 $1$ 行输出一个整数，表示最大乘积的位数。

第 $2$ 行输出最大乘积的前 $100$ 位；如果最大乘积不足 $100$ 位，则输出其全部位数。

在给定的数据范围内，最大乘积的位数不超过 $5000$ 位。

样例输入

13

样例输出

3
108

数据范围

• $10\le n\le 31000$。

来源与许可

本题为 SCOI 2006 试题「整数划分」，题面与测试数据整理自 BZOJ 1263。

样例 1

输入

13

输出

3
108