[SCOI2006] 整数划分
题目描述
从文件中读入一个正整数 $n$($10 \le n \le 31000$)。要求将 $n$ 写成若干个正整数之和,并且使这些正整数的乘积最大。
例如,$n=13$,则当 $n$ 表示为 $4+3+3+3$(或 $2+2+3+3+3$)时,乘积 $=108$ 为最大。
输入输出格式
输入格式
一行一个正整数 $n$。
输出格式
第 $1$ 行输出一个整数,为最大乘积的位数。
第 $2$ 行输出最大乘积的前 $100$ 位,如果不足 $100$ 位,则按实际位数输出最大乘积。
输入输出样例
输入样例 #1
13
输出样例 #1
3
108
说明
### 数据范围及约定
对于全部数据,$10 \le n \le 31000$,同时保证最大乘积的位数不超过 $5000$ 位。