Description

Read a positive integer $n$ from the file ($10 \le n \le 31000$). You need to write $n$ as a sum of several positive integers, and make the product of these integers as large as possible.

For example, when $n=13$, if $n$ is written as $4+3+3+3$ (or $2+2+3+3+3$), the product $=108$ is maximal.

Input Format

One line with a positive integer $n$.

Output Format

Line 1: output an integer, the number of digits of the maximum product.

Line 2: output the first 100 digits of the maximum product. If it has fewer than 100 digits, output the maximum product with its actual number of digits.

13

3
108

Hint

Constraints

For all testdata, $10 \le n \le 31000$, and it is guaranteed that the number of digits of the maximum product does not exceed 5000 digits.

Translated by ChatGPT 5