选择乘法

题目描述

给你一个整数 $N$。请考虑将 $N$ 的各数位重新排列，并分割成两个正整数。

例如，对于整数 $123$，有六种分割方式，如下所示：

$12$ 和 $3$，

$21$ 和 $3$，

$13$ 和 $2$，

$31$ 和 $2$，

$23$ 和 $1$，

$32$ 和 $1$。

这里，分割后的两个整数不能含有前导零。例如，不允许将 $101$ 分割成 $1$ 和 $01$。另外，由于分割后的两个整数必须是正整数，因此也不允许将 $101$ 分割成 $11$ 和 $0$。

通过最优分割，得到的两个整数的乘积最大可能是多少？

输入格式

输入按以下格式从标准输入给出：

$N$

输出格式

输出分割后两个整数的乘积的最大可能值。

样例

123

63

如题目描述所述，共有六种分割方式：

$12$ 和 $3$，

$21$ 和 $3$，

$13$ 和 $2$，

$31$ 和 $2$，

$23$ 和 $1$，

$32$ 和 $1$。

这些分割对应的乘积依次为 $36$、$63$、$26$、$62$、$23$、$32$，其中最大的是 $63$。

1010

100

共有两种分割方式：

$100$ 和 $1$，

$10$ 和 $10$。

无论哪种方式，乘积都是 $100$。

998244353

939337176

数据范围

• $1 \le N \le 10^9$
• $N$ 含有两个或两个以上不为 $0$ 的数位。