Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
73 - ZOJ Monthly, December 2008 - A
Bernstein Polynomial

Time Limit: 10 Seconds      Memory Limit: 32768 KB

Bernstein polynomial is defined as

$ \Huge B_n(f)=\sum_{i=0}^n
	{f(\frac{i}{n}){n \choose i}x^i(1-x)^{n-i}},\quad n=1,2,\cdots, $

where $\Huge f(x)\in C_{[0,1]}$, and:
$ \Huge\lim\limits_{n\to\inf}B_n(f)=f(x),\quad\forall x\in[0,1]. $

A polynomial $\Huge p(x)=c_dx^d+\cdots+c_1x+c_0$ can be represent in format d cd cd-1 ... c1 c0 where cd can be zero only if d is zero.

Given a polynomial and n, your task is to calculate the corresponding Bernstein polynomial.

Input

A polynomial in a separate line, satisfying that 0 <= d < 64, all coefficients ci are integers in range [-16, 16]. Then an integer 0 < n < 65536 in a separate line.

Output

The corresponding Bornstein polynomial. The coefficients are in irreducible fraction. See sample for more details.

Sample Input

0 -1
1
3 1 0 0 0
3

Sample Output

0 -1/1
3 2/9 2/3 1/9 0/1

Author: WU, Zejun
Source: ZOJ Monthly, December 2008
Submit    Status