Time Limit: 1 sec
Memory Limit: 32 MB
John likes mathematics a lot. His main passion is the binomial theorem. However it is rather hard to calculate binomial coefficients, so he decided to write a computer program that can expand any power of a sum into a sum of powers. Mathematically it can be written like this:
(a+b)k = x1ak + x2ak−1b + x3ak−2b2 + … + xk+1bk
where x1 … k+1 are binomial coefficients xi = Cki .
There is a number of tests T (T ≤ 100) on the first line. After T
test follows. Each test is written on a single line in form of (a+b)^k
. Where a
and b
are same variables names. Variables names are strings constructed from ’a
’–’z
’ characters. And k
(1 ≤ k ≤ 50) is a power that you need to raise the sum. You can assume that there are no lines longer than 100 characters.
For each test output a single line "Case N: T
". Where N
is the test number (starting from 1) and T
is an expanded expression (see examples for clarification). By the way, you shouldn’t output coefficients and powers equal to one.
3 (a+b)^1 (alpha+omega)^2 (acm+icpc)^3
Case 1: a+b Case 2: alpha^2+2*alpha*omega+omega^2 Case 3: acm^3+3*acm^2*icpc+3*acm*icpc^2+icpc^3