Already been college students, Jack and Rose start to work out problems of discrete mathematics.

Jack emerges great interest in rooted tree, which is a kind of directed tree that has a root vertex.

In a rooted tree, define the depth of vertex depth(u) as the number of edges between root vertex and . And the depth of a rooted tree is the maximum depth among all vertices of this tree.

The problem is to count the number of rooted trees that have n vertices, whose depth are not more than two, and are not isomorphism with each other. The answer should module .

: Rooted tree and are isomorphism if and only if there exists such a bijection that satisfying to any , when and only when .

: A kind of function between the elements of two set, where each element of one set is paired with exactly one element of the other set, and each element of the other set is paired with exactly one element of the first set.

The only line contains one integer  () --- the number of vertices.

Output a single integer --- the answer of the problem described above.

5

5