from itertools import permutations
 
t = [[0 for j in range(i)] for i in range(10)]
 
for n in range(1, 10):
	for p in permutations(range(1,n+1)):
		c = 0
		for i in range(n-1):
			if p[i+1] == p[i]+1:
				c += 1
		t[n][c] += 1
 
for i in t:
	for j in i:
		print "%6d" %j,
	print
print
 
dp = [[-1 for j in range(i)] for i in range(10)]
dp[1][0] = 1
 
def f(n,k):
	if not( 0 <= k <= n-1 ):
		return 0
	if dp[n][k] != -1:
		return dp[n][k]
	dp[n][k] = (k+1)*f(n-1,k+1)+(n-1-k)*f(n-1,k)+f(n-1,k-1)
	return dp[n][k]
 
for n in range(10):
	for k in range(n):
		print "%6d" %f(n,k),
	print
print

ZnJvbSBpdGVydG9vbHMgaW1wb3J0IHBlcm11dGF0aW9ucwoKdCA9IFtbMCBmb3IgaiBpbiByYW5nZShpKV0gZm9yIGkgaW4gcmFuZ2UoMTApXQoKZm9yIG4gaW4gcmFuZ2UoMSwgMTApOgoJZm9yIHAgaW4gcGVybXV0YXRpb25zKHJhbmdlKDEsbisxKSk6CgkJYyA9IDAKCQlmb3IgaSBpbiByYW5nZShuLTEpOgoJCQlpZiBwW2krMV0gPT0gcFtpXSsxOgoJCQkJYyArPSAxCgkJdFtuXVtjXSArPSAxCgpmb3IgaSBpbiB0OgoJZm9yIGogaW4gaToKCQlwcmludCAiJTZkIiAlaiwKCXByaW50CnByaW50CgpkcCA9IFtbLTEgZm9yIGogaW4gcmFuZ2UoaSldIGZvciBpIGluIHJhbmdlKDEwKV0KZHBbMV1bMF0gPSAxCgpkZWYgZihuLGspOgoJaWYgbm90KCAwIDw9IGsgPD0gbi0xICk6CgkJcmV0dXJuIDAKCWlmIGRwW25dW2tdICE9IC0xOgoJCXJldHVybiBkcFtuXVtrXQoJZHBbbl1ba10gPSAoaysxKSpmKG4tMSxrKzEpKyhuLTEtaykqZihuLTEsaykrZihuLTEsay0xKQoJcmV0dXJuIGRwW25dW2tdCgpmb3IgbiBpbiByYW5nZSgxMCk6Cglmb3IgayBpbiByYW5nZShuKToKCQlwcmludCAiJTZkIiAlZihuLGspLAoJcHJpbnQKcHJpbnQ=

MTA=

10