SPOJ Problem Set (classical)
1722. Life, the Universe, and Everything II
Problem code: RP

This problem tests your mathematic knowledge and your programming ability very much. Your task is to calculate the number of different Minimum Spanning Trees (MSTs) of a special undirected unweighted graph. The graph has n nodes numbered from 1 to n, and there is an edge between node i (1<=i<=n) and node j (1<=j<=n) if and only if 0<ij<=k.
Input
Multiple test cases, the number of them(<=8) is given in the very first line.
Each test case contains one line with two spaceseparated numbers k(1<=k<=5) and n(1<=n<=10^{15}).
Output
For each test case you should output one line, the number of different MSTs of the corresponding graph modulo 65521.
Example
Input:
1
3 5
Output:
75
Added by:  [Trichromatic] XilinX 
Date:  20070804 
Time limit:  0.162s0.469s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster: 
Cube (Intel Pentium G860 3GHz)

Languages:  All except: C99 strict ERL JS 
Resource:  Chinese National Olympiad in Informatics 2007,Day 2; Translated by Blue Mary 
