Rhyme scheme

Consider a stanza of poetry consisting of n lines. It all lines are divided into several classes within each of which lines rhyme with each other. In this problem we shall consider only those verses in which every line rhymes with at least one other.

For example, for the quatrains, there are four possible rhyming schemes that satisfy the preceding paragraph. This scheme AABB, ABAB, ABBA and AAAA.

For a given size stanza count the number of different rhyming schemes.

Input

In the input file contains a positive integer n, not exceeding 26.

Output

The output file output the number of rhyme schemes applicable to the n-poetry.

Examples