题目描述

给定一个正整数 $M$和一个只包含数字的字符串。使用 $M$个乘号插入到字符串中，且两个乘号不能相邻，插入后生成一个乘法算式。找出一种使乘法算式数值最大的插入方式，并将结果输出。(乘号不能放在字符串的首尾位置)

如M=2，字符串为 123456，插入 2个乘号。

插入方式有:

1*2*3456=6912，

1*23*456=10488，

1*234*56=13104，

1*2345*6=14070,

12*3*456=16416，

12*34*56=22848，

12*345*6=24840，

123*4*56=27552

123*45*6=33210，

1234*5*6=37020

其中乘法算式数值最大是第十种，为 37020

输入

第一行输入一个正整数 $M$，表示乘号个数

第二行输入一个只包含数字的字符串，表示要插入 $M$ 个乘号的字符串

输出

输出一个整数，表示最大乘积数值

2
123456

37020

提示

$(1<=M<=5)$

$(5<字符串长度<=15)$

蓝桥原本题目的范围是字符串长度小于等于20，为了避免写高精度，将本题范围缩小到字符串长度小于等于15