Rhyme scheme#1858

Rhyme scheme

0.5 seconds

256 megabytes

Medium

Consider a stanza of poetry consisting of $n$ lines. All lines are divided into several classes, and within each class, the lines rhyme with each other. In this problem, we shall consider only those stanzas in which every line rhymes with at least one other line.

For example, for quatrains, there are four possible rhyme schemes that satisfy the above conditions: AABB, ABAB, ABBA, and AAAA.

Count the number of different rhyme schemes for a stanza of a given size.

Input

The input file contains a positive integer $n$ , $n \leq 26$ n \leq 26.

Output

In the output file, output the number of rhyme schemes applicable to a stanza of $n$ lines.

Examples

Example 1

Loading

n \leq 26