# UVa 10843

## 10843 - Anne's game[edit]

## Summary[edit]

For this problem, we have to find the number of labeled trees on *N* vertices, modulo 2000000011.

## Explanation[edit]

Each circle is a vertex and each line drawn is an edge. Clearly after *N* steps we have a connected graph with *N* vertices and *N-1* edges. Thus the resulting graph is a tree. It can be proved that there are exactly labeled trees on N vertices. Since we only have to print the answer modulo 2000000011, this can be safely calculated without the use of BigNum.

## Implementation[edit]

While the answer fits into a 32-bit signed integer, using 64-bit integers is recommended when computing the result to avoid overflow.

## Notes[edit]

The answer can be computed in time using Repeated Squaring.

An exceptionally nice proof that the number of labeled trees on *N* vertices is can de achieved using the Prufer code of a tree.

## Input[edit]

3 1 2 3

## Output[edit]

Case #1: 1 Case #2: 1 Case #3: 3