Codechef May 2013 Tree

	# a dive into the deep, a lot of concepts here
	# Kirchoff's Matrix Tree Theorem, Laplacian matrix, cofactors, a revision into
	# determinants
	# Revision: replacing a row by itself minus a multiple of another row:
	# doesn't change determinant
	# k=3, A =
	# 0,0,0,1,1,1,1,1,1.......1
	# 0,0,0,1,1,1,1,1,1.......1
	# 0,0,0,1,1,1,1,1,1.......1
	# 1,1,1,0,0,0,1,1,1.......1
	# 1,1,1,0,0,0,1,1,1.......1
	# 1,1,1,0,0,0,1,1,1.......1
	# 1,1,1,1,1,1,0,0,0.......1
	# 1,1,1,1,1,1,0,0,0.......1
	# 1,1,1,1,1,1,0,0,0.......1
	# ............
	# ............
	# 1,1,1,1,1,1,1,1,1,1,0,0,0
	# D =
	# 3n-3,0,0,0,0,0,.....
	# 0,3n-3,0,0,0,0,0,0..
	# 0,0,3n-3,0,0,0,0,0..
	# ....
	# ....
	# 0,0,0,0,0........0,0,3n-3
	# Laplacian matrix = D - A
	# =
	# 3n-3,0,0,-1,-1,-1,-1,-1,-1,-1....-1
	# 0,3n-3,0,-1,-1,-1,-1,-1,-1,-1....-1
	# 0,0,3n-3,-1,-1,-1,-1,-1,-1,-1....-1
	# .....
	# -1,-1,-1,-1,-1,-1,-1...........3n-3
	# taking away last row, and column
	# Laplacian matrix = D - A
	# =
	# 3n-3,0,0,-1,-1,-1,-1,-1,-1,-1....-1
	# 0,3n-3,0,-1,-1,-1,-1,-1,-1,-1....-1
	# 0,0,3n-3,-1,-1,-1,-1,-1,-1,-1....-1
	# .....
	# -1,-1,-1,-1,.......0,3n-3,0,-1-1
	# -1,-1,-1,-1,.......0,0,3n-3,-1-1
	# -1,-1,-1,-1,-1,-1,-1........3n-3,0
	# -1,-1,-1,-1,-1,-1,-1........0,3n-3
	# =
	# 3n-3,3-3n,0,0,0,0,0............0 normalized = 1,-1,0000
	# 0,3n-3,3-3n,0,0,0,0............0 normalized = 0,1,-1,00
	# 1,1,3n-2,2-3n,-1,-1,0,0,0......0 -= row1 + row2*2
	# 0,0,0,3n-3,3-3n,0,0,0,0,0......0 # same
	# 0,0,0,0,3n-3,3-3n,0,0,0,0......0 # same
	# 0,0,0,1,1,3n-2,2-3n,-1,-1,0,0..0 # same
	# ....
	# 0,0,0..............3n-2,2-3n,-1
	# 0,0,0..................3n-3,3-3n
	# -1,-1,-1,-1,-1,-1........0,3n-3
	# =
	# 3n-3,3-3n,0,0,0,0,0............0
	# 0,3n-3,3-3n,0,0,0,0............0
	# 0,0,3n,2-3n,-1,-1,0,0,0........0
	# 0,0,0,3n-3,3-3n,0,0,0,0,0......0
	# 0,0,0,0,3n-3,3-3n,0,0,0,0......0
	# 0,0,0,0,0,3n,2-3n,-1,-1,0,0....0
	# ....
	# 0,0,0.................3n,2-3n,-1
	# 0,0,0..................3n-3,3-3n
	# -1,-1,-1,-1,-1,-1........0,3n-3
	# =
	# 3n-3,3-3n,0,0,0,0,0............0
	# 0,3n-3,3-3n,0,0,0,0............0
	# 0,0,3n,-3n,0,0,0,0,0...........0
	# 0,0,0,3n-3,3-3n,0,0,0,0,0......0
	# 0,0,0,0,3n-3,3-3n,0,0,0,0......0
	# 0,0,0,0,0,3n,-3n,0,0,0,0.......0
	# ....
	# 0,0,0.................3n,2-3n,-1
	# 0,0,0..................3n-3,3-3n
	# -1,-1,-1,-1,-1,-1........0,3n-3
	# =
	# 3n-3,3-3n,0,0,0,0,0............0 = 1,-1, 0, 0, 0 * 1
	# 0,3n-3,3-3n,0,0,0,0............0 = 0, 1,-1, 0, 0 * 2
	# 0,0,3n,-3n,0,0,0,0,0...........0 = 0, 0, 1,-1, 0 * 3
	# 0,0,0,3n-3,3-3n,0,0,0,0,0......0 = 0, 0, 0, 1,-1 * 4
	# 0,0,0,0,3n-3,3-3n,0,0,0,0......0 ......
	# 0,0,0,0,0,3n,-3n,0,0,0,0.......0
	# ....
	# ......... .0,0,0,3n-3,3-3n, 0, 0 = ............1,-1 * (3n-4)
	# 0,0,0..................3n,1-3n,0
	# 0,0,0..................3n-3,3-3n
	# -1,-1,-1,-1,-1,-1...-1,-1,0,3n-3
	# =
	# 3n-3,3-3n,0,0,0,0,0............0
	# 0,3n-3,3-3n,0,0,0,0............0
	# 0,0,3n,-3n,0,0,0,0,0...........0
	# 0,0,0,3n-3,3-3n,0,0,0,0,0......0
	# 0,0,0,0,3n-3,3-3n,0,0,0,0......0
	# 0,0,0,0,0,3n,-3n,0,0,0,0.......0
	# ....
	# 0,0,0..................3n,1-3n,0
	# 0,0,0................0,3n-3,3-3n
	# 0,0,0................3-3n,0,3n-3
	# =
	# 3n-3,3-3n,0,0,0,0,0............0
	# 0,3n-3,3-3n,0,0,0,0............0
	# 0,0,3n,-3n,0,0,0,0,0...........0
	# 0,0,0,3n-3,3-3n,0,0,0,0,0......0
	# 0,0,0,0,3n-3,3-3n,0,0,0,0......0
	# 0,0,0,0,0,3n,-3n,0,0,0,0.......0
	# ....
	# 0,0,0...................3n,1-3n,0
	# 0,0,0..................0,3n-3,3-3n = 0,1,-1
	# 0,0,0..................3-3n,0,3n-3 = -1,0,1
	# =
	# 3n-3,3-3n,0,0,0,0,0............0
	# 0,3n-3,3-3n,0,0,0,0............0
	# 0,0,3n,-3n,0,0,0,0,0...........0
	# 0,0,0,3n-3,3-3n,0,0,0,0,0......0
	# 0,0,0,0,3n-3,3-3n,0,0,0,0......0
	# 0,0,0,0,0,3n,-3n,0,0,0,0.......0
	# ....
	# 0,0,0..................1,0,0
	# 0,0,0..................0,3n-3,3-3n
	# 0,0,0..................3-3n,0,3n-3
	# =
	# 3n-3,3-3n,0,0,0,0,0............0
	# 0,3n-3,3-3n,0,0,0,0............0
	# 0,0,3n,-3n,0,0,0,0,0...........0
	# 0,0,0,3n-3,3-3n,0,0,0,0,0......0
	# 0,0,0,0,3n-3,3-3n,0,0,0,0......0
	# 0,0,0,0,0,3n,-3n,0,0,0,0.......0
	# ....
	# 0,0,0..................1,0,0
	# 0,0,0..................0,3n-3,3-3n
	# 0,0,0..................0,0,3n-3
	# cofactor(3n,3n) = (3n-3)^(2n) * (3n)^(n-2)
	# finally correct; spent 3 hours figuring this out
	import sys
	def modular_exponent(a,b,n):
	binary = ""
	while b > 0:
	if b & 1 == 0:
	binary += "0"
	else:
	binary += "1"
	b >>= 1
	result = 1
	for k in xrange(len(binary)):
	result = (result * result) % n
	if binary[len(binary)-k-1] == "1":
	result = (result * a) % n
	return result
	T = sys.stdin.readline().strip()
	n,k = T.split()
	n = int(n)
	k = int(k)
	print (modular_exponent(k*(n-1),n*(k-1),10**9+7)* modular_exponent(k*n,n-2,10**9+7)) % (10**9+7)

view raw gistfile1.txt hosted with ❤ by GitHub