小泽正在学习位值展开。一个 $M$ 进制数的每一位，都可以写成“该位数码乘以 $M$ 的相应次幂”。例如 $(10101)_2$ 可写为 1*2^4+1*2^2+1*2^0。

给出进制 $M$ 和一个只含十进制数字字符的合法 $M$ 进制数 $N$，请输出它的位值展开式。系数为 $0$ 的项必须省略，项之间用 + 连接。

输入格式

输入一行两个整数形式的数据 $M,N$。

输出格式

输出省略零系数项后的位值展开式，格式为 系数*进制^指数。

2 10101

1*2^4+1*2^2+1*2^0

7 604

6*7^2+4*7^0

9 1000001

1*9^6+1*9^0

数据范围

• $2\le M\le9$
• $N$ 的每一位小于 $M$，且 $N>0$