import copy
import timeit

#Funzioni di utilita'
def scambia(a, i, j):
	a[i], a[j] = a[j], a[i]

def perm(ps, a, i):
	if i == len(a):		
		ps.append(copy.copy(a))
	for j in range(i, len(a)):
		scambia(a, i, j)
		perm(ps, a, i+1)
		scambia(a, i, j)

def printMatPlus(q):
	for i in range(len(q)):
		for j in range(len(q)):
			print q[i][j],
		print	
	print	

def printMat(q):
	for i in range(len(q)):
		print q[i]
	print	


# genera le sequenze binarie per rappresentare 
# come vettori caratteristici tutti gli (n su k) sottoinsiemi 
# usata a costruire le n-tuple di n-tuple di sequenze magiche.
def cbn(n,k):
	cs = []
	s = [0 for _ in range(n)]
	cbnAux(s,0,n,k,cs)
	return cs

def cbnAux(s,i,n,k,cs):
	if k==0:
		cs.append(copy.copy(s))
		return
	if i==n:
		return
	s[i]=1
	cbnAux(s,i+1,n,k-1,cs)
	s[i]=0
	cbnAux(s,i+1,n,k,cs)

def kmagica(n):
	km = n * (n * n +1) // 2
	return km
	
def nTuple(v, t, i, j, k, km,res):
# calcola le k-uple a somma km (sequenze magiche)
#	print v, t, i, j, k, km
	global s
	if k==0 and km == 0:
		s = s + 1
		res = res.append(copy.copy(t))
		return True
	if km < 0 or i==len(v) or v[i]>km or j==len(t):
		return False
	t[j] = v[i]	
	nTuple(v,t,i+1,j+1,k-1,km-v[i],res)
	nTuple(v,t,i+1,j,k,km,res)

def initQ(n):
	q = [i+1 for i in range(n*n)]
	sr = [0 for _ in range(n)]
	sc = [0 for _ in range(n)]
	return q, sr, sc

def disjoint(x,y):
# verifica se due liste ordinate sono disgiunte	
	i, j = 0, 0
	while i<len(x) and j<len(y):
		if x[i]==y[j]:
			return False
		elif x[i]<y[j]:
			i = i+1
		else: 
			j = j+1
	return True

def disjointSet(s, x):
	for y in s:
		if not disjoint(x, y):
			return False
	return True
			
def allDisjoint(x,n):
# versione errata di calcolo delle n-uple 
# di sequenze magiche: se ne perde un bel po'...	
	r = 0
	for i in range(len(x)):
		if x[i][0]!=1:
			break
		s = [copy.copy(x[i])]
		for j in range(i+1,len(x)):
			if disjointSet(s,x[j]):
				s.append(copy.copy(x[j]))
				if len(s) == n:
					if r==0:
						allS = [copy.copy(s)]
					else:
						allS.append(copy.copy(s))
					r = r+1
					break
	return allS, r				

def allDisjointNew(x,n):
# esamina tutti i sottoinsiemi di cardinalita' n di 
# sequenze magiche	
	allS = []
	cs = cbn(len(x),n)
	for cars in cs:
		s = []
		ok = True
		for i in range(len(cars)):
			if cars[i]:
				if disjointSet(s,x[i]):
					s.append(copy.copy(x[i]))
				else: 
					ok = False
					break
		if ok:
			allS.append(copy.copy(s))			
	return allS		

def sistema(ss, q, n, r, pr, ps, d, sc, km):
#questa funzione sistema la riga r di q
#provando tutte le permutazioni di ss[p[r]]
#controlla i vincoli su somma colonne (sc) e diagonali (d)
	global nq
	if r == n:
		if d[0] == km and d[1] == km:
			 nq = nq + 1
			 print "Eureka! ",nq			
			 printMatPlus(q)
			 print sc
		return
	for prm in ps:
		ok = True	
		for i in range(n):
			q[r][i] = ss[pr[r]][prm[i]]
			sc[i] = sc[i] + q[r][i]
			if sc[i]>km: #or sc[i] < km - (n - r)*n*n:
				ok = False
		d[0]=d[0]+q[r][r]
		d[1]=d[1]+q[r][n-r-1]
		if d[0] > km or d[1] > km:
			ok = False
		if ok:
			sistema(ss,q,n,r+1,pr,ps,d,sc,km)
		# toglie la riga appena messa	
		d[0]=d[0]-q[r][r]
		d[1]=d[1]-q[r][n-r-1]
		for i in range(n):
			sc[i] = sc[i] - q[r][i]
			q[r][i] = 0

def allQs(ss,n,ps,km):
# ss e' un insieme compatibile di righe magiche
	q = [[0 for _ in range(n)] for _ in range(n)]	
	d = [0,0]
	sc = [0 for _ in range(n)]
	for pr in ps:
		sistema(ss, q, n, 0, pr, ps, d, sc, km)

def allQms(sss,n,ps,km):
	for ss in sss:
		allQs(ss,n,ps,km)

nq = 0
s = 0
n = 4
ps = []
perm(ps,range(n),0)

km=kmagica(n)
q, sr, sc = initQ(n)
res = []
t = [0 for _ in(range(n))]
nTuple(q,t,0,0,n,km,res)
#print res
#allS, raws = allDisjoint(res,n)
#print raws," :",allS
allS = allDisjointNew(res,n)
print len(allS)
#print len(allS)," : ", allS
allQms(allS,n,ps,km)
#print n, km, s, raws
#tempo = timeit.timeit(lambda: allQms(allS,n,ps,km), number=1)
#print tempo
print nq