Hacker cup 2013 final problem 2

Topics here are only Rebol 2 related

Hacker cup 2013 final problem 2

Postby MaxV on Thu May 16, 2013 9:47 am

Rebol is admintted as language in Hacker cup 2013! Can you solve this problem?

You are given two integers N and K, 1 ≤ N ≤ 1000, 1 ≤ K ≤ 10E9. Your task is to calculate how many distinct trees with N vertices there are with each vertex colored with one of K colors. Multiple vertices can have the same color, and not all colors need to be used. Two trees t1 and t2 are considered identical if there exists a bijective function f from vertices of t1 to vertices of t2 such that each vertex x in t1 is colored the same as f(x) in t2 and each pair of vertices x, y in t1 is connected by an edge if and only if f(x) and f(y) are connected by an edge in t2. A bijective function is a function that is both one-to-one and onto, meaning that f(x) = f(y) if and only if x = y, and for every vertex y in t2, there exists x in t1, such that f(x) = y.

Input

The first line contains a single integer T, T ≤ 20. T test cases follow, where each test case consists of two integers: N and K.

Input is a TXT file (uncompress it):
colored_trees.zip
(278 Bytes) Downloaded 21 times


Output

Output one single line with the number of colored trees. Since this number might be very big, output it modulo 1,000,000,007.

Examples
fhc2.png
fhc2.png (86.99 KB) Viewed 371 times

Example input

Code: Select all
5
1 1
2 10
4 1
3 2
6 6

Example output
Code: Select all
Case #1: 1
Case #2: 55
Case #3: 2
Case #4: 6
Case #5: 96237
User avatar
MaxV
 
Posts: 104
Joined: Tue Jan 22, 2013 12:04 pm
Location: Italy

Return to Rebol 2

Who is online

Users browsing this forum: No registered users and 1 guest

cron