Codechef May 2013 Tree

gistfile1.txt

# 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)