提示: 欢迎访问OurACM平台。
Problem 2215 Simple Polynomial Problem

Accept: 153    Submit: 448
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

You are given an polynomial of x consisting of only addition marks, multiplication marks, brackets, single digit numbers, and of course the letter x. For example, a valid polynomial would be: (1+x)*(1+x*x+x+5)+1*x*x.

You are required to write the polynomial into it's minimal form by combining the equal terms.

For example, (1+x)*(1+x) would be written as x^2+2*x+1.

Also, (1+x)*(1+x*x+x+5)+1*x*x would be written as x^3+3*x^2+7*x+6.

Input

The first line contains an integer T, meaning the number of the cases. 1 <= T <= 50.

For each test case, there will be one polynomial which it's length would be not larger than 1000.

It is guaranteed that every input polynomial is valid, and every number would be a single digit.

Output

For each polynomial, output it's minimal form. If the polynomial's minimal form has n terms, output n space-separated integers.

You only have to output each term's corresponding constant (from highest to lowest). In case the constant gets too big, output the remainder of dividing the answer by 1000000007 (1e9 + 7).

Sample Input

4 1*(1+1*(1+1)) (1+x)*(1+x) x*((1+x)*(1+x*x+x+5)+1*x*x) (x*x*x*0+x*2)*x

Sample Output

3 1 2 1 1 3 7 6 0 2 0 0

Source

第六届福建省大学生程序设计竞赛-重现赛(感谢承办方华侨大学)

Submit  Back  Status  Discuss