# UVa 10843

## Summary

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

## Explanation

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 ${\displaystyle N^{N-2}}$ 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

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

## Notes

The answer can be computed in ${\displaystyle O(\log n)}$ time using Repeated Squaring.

An exceptionally nice proof that the number of labeled trees on N vertices is ${\displaystyle N^{N-2}}$ can de achieved using the Prufer code of a tree.

```3
1
2
3
```

## Output

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