zero = {}                
one = {0:1}
two = {0:2}
x = {1:1}
x2 = {2:1}                  # x^2
poly = {2:3, 1:4, 0:5}   # 3*x^2 + 4*x + 5

def add_poly(poly1, poly2):   # w1(x)+w2(x)
	tmp = dict(poly1)
	for k in poly2:

		tmp[k] = tmp.get(k,0) + poly2[k]
		if tmp[k] == 0: del tmp[k]
	return tmp

def times_poly(number, poly):   # n*w(x)
	if number == 0: return {}
	tmp = {}
	for k in poly:
		tmp[k] = number*poly[k]

	return tmp

def mul_poly(poly1, poly2):   # w1(x)*w2(x)
	tmp = {}
	for i in poly1:
		for j in poly2:
			tmp[i+j] = tmp.get(i+j,0) + poly1[i]*poly2[j]
	return tmp

def diff_poly(poly):   #  [c*x^n]' = c*n*x^(n-1)

	tmp = {}
	for i in poly:
		tmp[i-1] = i*poly[i]
	if -1 in tmp: del tmp[-1]
	return tmp

def eval_poly(poly, x):   # w(x), Horner
	i = max(i for i in poly)
	p = poly[i]
	while i > 0:
		i = i-1

		p = p * x + poly.get(i,0)
	return p

def combine_poly(poly1, poly2):   # w1(w2(x)),  Horner
	i = max(k for k in poly1)
	tmp = {0:poly1[i]}
	while i > 0:
		i = i-1
		tmp = add_poly(mul_poly(tmp, poly2), {0:poly1.get(i,0)})

	return tmp

def pow_poly(poly, n):
	# return combine_poly({n:1}, poly)
	tmp = {0:1}
	while n > 0:
		tmp = mul_poly(tmp, poly)
		n = n-1
	return tmp