#div()内でリストをコピーする必要があるのでインポート
import copy

def deg(a):return len(a)-1

def mul(a,b):
	A=deg(a)
	B=deg(b)
	f=[0]*(A+B+1)
	for i in range(A+B+1):
		for j in range(max(0,i-B),min(i,A)+1):
			f[i]=(f[i]+a[j]*b[i-j])%p
	return f

#mod pにおいて多項式aを多項式bでで割った商を返す(余る場合は[0]を返す)
def div(aa,b,p):
	
	#この関数内でaaを変更すると、使用時に引数として与えたリストにも反映されてしまうので、コピーを作ってそれを扱う
	a=copy.deepcopy(aa)

	#次数を計算しておく
	A=deg(a)
	B=deg(b)

	#自明
	if A<B:
		return[0]
	
	#非自明を含む
	else:
	
		#商を格納するリストqを用意
		q=[0]*(A-B+1)

		#商を最高次から順に定める
		for i in range(A-B+1):

			#(bの最高次係数)*(商の定めたい係数)とa[i]とがpを法として合同であるように商の係数を定める
			for j in range(p):
				if (b[0]*j-a[i])%p==0:
					q[i]=j
			
			#被除多項式aの次数を落とす
			for j in range(0,B+1):
				a[i+j]=(a[i+j]-b[j]*q[i]+p*p)%p

		#余りをチェックして0でない係数があれば[0]を返す
		for i in range(A+1):
			if a[i]!=0:
				return[0]

		#商を返す
		return q


def gau(a):return deg(a)//2

def bun(a,p):
	if deg(a)==0:
		return 0
	elif deg(a)==1:
		print(a)
		return 0
	for i in range(1,gau(a)+1):
		
		#因数の候補fを格納するリストを用意
		f=[0]*(i+1)

		#因数全探索
		c=p**i
		for pp in range(c,c+c):
			
			#p進数からfを構成する
			for j in range(i+1):
				f[j]=pp%p
				pp//=p

			#fの最高次の係数が0でなければ除算以降の処理を行う
			if f[0]!=0:
				
				#除算した結果をgに格納
				g=div(a,f,p)

				#割り切れていれば([0]が返っていなければ)fはaの因数であり、商gを因数分解する
				if g!=[0]:
					print(f)
					bun(g,p)
					return 0
	
	print(a)
	return 0
