SP1722 RP - Life, the Universe, and Everything II

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

Multiple test cases, the number of them(

For each test case you should output one line, the number of different MSTs of the corresponding graph modulo 65521.