### Problem Statement

Two polynomials are multiplied together by multiplying each term in the first polynomial with each term in the second polynomial, and adding all of these individual products together. For example:

```
(4*x^4 + 1) * (3*x^5 + 7*x)
= (4*x^4 * 3*x^5) + (4*x^4 * 7*x) + (1 * 3*x^5) + (1 * 7*x)
= 12*x^9 + 28*x^5 + 3*x^5 + 7*x
```

This can be simplified by combining the two x^5 terms:

```
= 12*x^9 + 31*x^5 + 7*x
```

Write a program which multiplies two polynomials, and simplifies the product by combining terms with the same exponent. Each polynomial will be a function of x, and will consist of one or more terms separated by " + " (a space, '+', and another space). Each term will be in one of the following forms:

```
1
#
x
x^#
#*x
#*x^#
(Each '#' character represents a single digit between '2' and '9', inclusive.)
```

Your program should return the product as a sum of terms, each in one of the formats above, except that the coefficients and exponents in your return value may be larger than a single digit. (Note that coefficients and exponents of 1 are omitted.) In between each term, insert the String " + " (a space, '+', and another space). You should output the terms in order from largest exponent of x to smallest exponent of x. If two or more terms have the same exponent, add their coefficients together to combine them into a single term.

### Definition

 Class: PolynomialMultiplier Method: product Parameters: String, String Returns: String Method signature: String product(String f1, String f2) (be sure your method is public)

### Notes

-The terms in the input functions will not necessarily be sorted by exponent of x.
-There may be multiple terms in the input function with the same exponent of x.

### Constraints

-f1 and f2 will each contain between 1 and 50 characters, inclusive.
-f1 and f2 will conform to the formatting rules in the problem statement.

### Examples

0)

 `"1 + x"` `"1 + x"`
`Returns: "x^2 + 2*x + 1"`
 ``` (1 + x) * (1 + x) = 1 + x + x + x*x = x^2 + 2*x + 1 ``` Remember to combine terms with equal exponents, and sort from greatest to smallest exponent.
1)

 `"4*x^4 + 1"` `"3*x^5 + 7*x"`
`Returns: "12*x^9 + 31*x^5 + 7*x"`
 This is the example from the problem statement.
2)

 `"1 + x + 1 + x"` `"5 + 5"`
`Returns: "20*x + 20"`
3)

 `"8*x^5"` `"9*x^7"`
`Returns: "72*x^12"`
4)

 `"5*x^3 + x^4 + 8 + 2*x^6"` `"3*x^5 + 4*x + 7*x^9"`
```Returns:
"14*x^15 + 7*x^13 + 35*x^12 + 6*x^11 + 59*x^9 + 15*x^8 + 8*x^7 + 28*x^5 + 20*x^4 + 32*x"```

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2418

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4760&pm=2418

legakis

#### Testers:

lbackstrom , brett1479

#### Problem categories:

Math, String Parsing