#469. 整数划分

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

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

一个正整数$n(1\le n \le 31000)$。

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

第 $1$ 行输出一个整数，为最大乘积的位数。 第 $2$ 行输出最大乘积的高位 $100$ 位，如果不足 $100$ 位，则按实际位数输出最大乘积。

输入样例1

13

输出样例1

3
108

输入样例2

1012

输出样例2

161
8218670649826245944980599366462354031861280648818440943263708399986549619544506955820876773013288043

提示
样例 $1$ 的解释已经在题目描述中给出。