import copy
def deg(a):return len(a)-1
def div(aa,b,p):
	a=copy.deepcopy(aa)
	A=deg(a)
	B=deg(b)
	if A<B:
		return[0]
	else:
		q=[0]*(A-B+1)
		for i in range(A-B+1):
			for j in range(p):
				if (b[0]*j-a[i])%p==0:
					q[i]=j
			for j in range(0,B+1):
				a[i+j]=(a[i+j]-b[j]*q[i]+p*p)%p
		for i in range(A+1):
			if a[i]!=0:
				return[0]
		return q
def fac(a,p):
	if deg(a)==0:
		return 0
	elif deg(a)==1:
		print(a)
		return 0
	for i in range(1,deg(a)//2+1):
		f=[0]*(i+1)
		c=p**i
		for pp in range(c,c+c):
			for j in range(i+1):
				f[j]=pp%p
				pp//=p
			if f[0]!=0:
				g=div(a,f,p)
				if g!=[0]:
					print(f)
					fac(g,p)
					return 0
	print(a)
	return 0