Counting Rotavirus Trees

A rotavirus is produced from a cyclic base (or n-rotamorphic base) consisting of n distinct outer atoms arranged in a circle and one central atom. Each pair of atoms is connected by an edge that represents an information channel. A valid n-rotavirus is constructed by removing some edges from the complete graph on these n+1 atoms so that there is exactly one unique path between any two atoms (i.e. the resulting graph is a tree).

In other words, given an n-rotamorphic base (with n atoms on the circle and one central atom), the construction rule is to choose a spanning tree of the complete graph on n+1 vertices. According to Cayley’s formula, the number of different trees on n+1 labeled vertices is given by:

$$(n+1)^{n-1}$$

For example, when n = 3, the number is $$4^{2} = 16$$, which corresponds to the 16 different 3-rotaviruses.

Your task is to compute the number of different n-rotavirus when given n (with n \le 100).

inputFormat

The input consists of a single integer n (1 \le n \le 100), representing the number of outer atoms in the cyclic base.

outputFormat

Output the number of different n-rotavirus, which is given by $$ (n+1)^{n-1} $$.

sample

1

1