Symmetric polynomials P75097

A polynomial p in three variables a, b and c is symmetric if and only if p(a, b, c) = p(a, c, b) = p(b, a, c) = … for the six permutations of the variables.

For example, a+b+c, ab+bc+ac, 3a²b²c² and 7abc+a²bc+ab²c+abc² are symmetric polynomials, while ab+ac and a²bc − ab²c + abc² are not.

We introduce the notation [a^i b^j c^k] with i ≥ j ≥ k to denote the symmetric polynomial that results from adding all the monomials of the form aⁱb^jc^k for any permutation of a, b and ‍c, where all the resulting monomials appear with coefficient 1. For example, [a] = a+b+c, [ab] = ab + bc + ca, and [a^2bc] = a²bc + ab²c + abc². (Note the special cases for the notation when the exponent of a variable is zero or one.)

Symmetric polynomials that do not have any variables of degree larger than one, that is, [a], [ab] and [abc], are called elementary symmetric polynomials. The fundamental theorem of symmetric polynomials, already known to Newton, states that any symmetric polynomial can be expressed as the sum and product of elementary symmetric polynomials.

Here, we don’t ask you to find these expressions. Instead, we ask you a much simpler task: calculate the product between a symmetric polynomial [a^i b^j c^k] and an elementary symmetric polynomial. (If you do this, you are not far away from establishing a recurrence relation and explicitly finding the expressions from the fundamental theorem.)

Input

Input consists of several cases, each with the product of a symmetric polynomial and an elementary symmetric polynomial. Assume i ≥ 1 and 0 ≤ k ≤ j ≤ i ≤ 1000.

Output

For every product, print its result. Make sure that the terms are in lexicographical order, that is, first the term with the largest i, and in case of a tie, first the term with the largest j.