Description

Write a program to rewrite an algebraic polynomial expression that contains a multiplication operation into an algebraic polynomial without multiplication. To simplify the task, we make the following conventions:

1. The algebraic polynomial expression involves only one algebraic symbol a.
2. It is guaranteed that the input “algebraic polynomial with multiplication” contains exactly one multiplication between an “algebraic polynomial” and an “algebraic polynomial”. Formally, in each test, the input has exactly one line (...)*(...), where ... is an algebraic polynomial without multiplication.
3. An “algebraic polynomial without multiplication” is written as XXXa^YYY+XXXa^YYY+XXXa^YYY+...+XXX (representing $\text{XXX}a ^ \text{YYY} + \text{XXX}a ^ \text{YYY} + \text{XXX}a ^ \text{YYY} + \cdots + \text{XXX}$), where XXX and YYY are positive integers. Moreover, except for the first term, in each subsequent term the YYY is exactly $1$ less than that of the previous term. For example, a valid “algebraic polynomial without multiplication” is 142a^4+9a^3+4a^2+1a^1+3.

For Convention 3, the original statement is: All non-constant terms are of the form $xa^y$, written as xa^y, where $x$ is the coefficient and $y$ is the exponent. When $x = 1$, it must not be abbreviated to a^y, and should be written as 1a^y. When $y = 1$, it must not be abbreviated to xa, and should be written as xa^1.

Input Format

The input consists of a single line string representing the given “algebraic polynomial with multiplication”.

Its format is: (...)*(...), where ... is an algebraic polynomial without multiplication. For the constraints on “algebraic polynomial without multiplication,” refer to the Description.

Output Format

Output a single string on one line representing the answer.

Terms with larger exponents must not appear after terms with smaller exponents, and terms with the same exponent must be combined. No unnecessary whitespace characters are allowed. No parentheses are allowed in the output.

(5a^2+3a^1+2)*(4a^1+1)
(5a^1+1)*(5a^1+1)

20a^3+17a^2+11a^1+2
25a^2+10a^1+1

Hint

Notes on Constraints and some format details:

• The ranges of coefficients and exponents are both $[0,30]$.

Translated by ChatGPT 5