Contest Duration: - (local time) (100 minutes) Back to Home
C - Select Mul /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

• 123
• 213
• 132
• 312
• 231
• 321

なお、ここで分離されたあとの 2 整数に leading zero が含まれていてはなりません。例えば、101 という整数を 1012 つに分離することはできません。また上述の「正整数に分離する」という条件より、1011102 つに分離することもできません。

### 制約

• N1 以上 10^9 以下の整数
• N には 0 でない桁が 2 つ以上含まれる

### 入力

N


### 入力例 1

123


### 出力例 1

63


• 123
• 213
• 132
• 312
• 231
• 321

### 入力例 2

1010


### 出力例 2

100


• 1001
• 1010

いずれの場合にも積は 100 となります。

### 入力例 3

998244353


### 出力例 3

939337176


Score : 300 points

### Problem Statement

You are given an integer N. Consider permuting the digits in N and separate them into two positive integers.

For example, for the integer 123, there are six ways to separate it, as follows:

• 12 and 3,
• 21 and 3,
• 13 and 2,
• 31 and 2,
• 23 and 1,
• 32 and 1.

Here, the two integers after separation must not contain leading zeros. For example, it is not allowed to separate the integer 101 into 1 and 01. Additionally, since the resulting integers must be positive, it is not allowed to separate 101 into 11 and 0, either.

What is the maximum possible product of the two resulting integers, obtained by the optimal separation?

### Constraints

• N is an integer between 1 and 10^9 (inclusive).
• N contains two or more digits that are not 0.

### Input

Input is given from Standard Input in the following format:

N


### Output

Print the maximum possible product of the two integers after separation.

### Sample Input 1

123


### Sample Output 1

63


As described in Problem Statement, there are six ways to separate it:

• 12 and 3,
• 21 and 3,
• 13 and 2,
• 31 and 2,
• 23 and 1,
• 32 and 1.

The products of these pairs, in this order, are 36, 63, 26, 62, 23, 32, with 63 being the maximum.

### Sample Input 2

1010


### Sample Output 2

100


There are two ways to separate it:

• 100 and 1,
• 10 and 10.

In either case, the product is 100.

### Sample Input 3

998244353


### Sample Output 3

939337176