Symmetric and Transitive
Contest: Codeforces Round 315 (Div. 1)
Difficulty rating: 1900
Tags: combinatorics, dp, math

Little Johnny has recently learned about set theory. Now he is studying binary relations. You've probably heard the term "equivalence relation". These relations are very important in many areas of mathematics. For example, the equality of the two numbers is an equivalence relation.

A set ρ of pairs (a, b) of elements of some set A is called a binary relation on set A. For two elements a and b of the set A we say that they are in relation ρ, if pair $$(a,b)\in\rho$$, in this case we use a notation $$a \stackrel{\rho}{\sim} b$$.

Binary relation is equivalence relation, if:

1. It is reflexive (for any a it is true that $$a^{\rho}\approx a$$);
2. It is symmetric (for any a, b it is true that if $$a \stackrel{\rho}{\sim} b$$, then $$b \stackrel{\rho}{\sim} a$$);
3. It is transitive (if $$a \stackrel{\rho}{\sim} b$$ and $$b \sim c$$, than $$a \stackrel{\rho}{\sim} c$$).

Little Johnny is not completely a fool and he noticed that the first condition is not necessary! Here is his "proof":

Take any two elements, a and b. If $$a \stackrel{\rho}{\sim} b$$, then $$b \stackrel{\rho}{\sim} a$$ (according to property (2)), which means $$a^{\rho}\approx a$$ (according to property (3)).

It's very simple, isn't it? However, you noticed that Johnny's "proof" is wrong, and decided to show him a lot of examples that prove him wrong.

Here's your task: count the number of binary relations over a set of size n such that they are symmetric, transitive, but not an equivalence relations (i.e. they are not reflexive).

Since their number may be very large (not 0, according to Little Johnny), print the remainder of integer division of this number by 109 + 7.

Input format:
A single line contains a single integer n (1 ≤ n ≤ 4000).

Output format:
In a single line print the answer to the problem modulo 109 + 7.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
If n = 1 there is only one such relation — an empty one, i.e. $$\varphi=\emptyset$$. In other words, for a single element x of set A the following is hold: $$x^{\rho}x^{r}$$.

If n = 2 there are three such relations. Let's assume that set A consists of two elements, x and y. Then the valid relations are $$\varphi=\emptyset$$, ρ = {(x, x)}, ρ = {(y, y)}. It is easy to see that the three listed binary relations are symmetric and transitive relations, but they are not equivalence relations.

Example input:
1

Example output:
1

Example input:
2

Example output:
3

Editorial:
Давайте сначала разберёмся, в чем же конкретно неправ Вовочка. В доказательстве хорошо всё, кроме того, что мы сразу взяли a, b такие, что $$a \stackrel{\rho}{\sim} b$$. Если такие есть, то действительно $$a^{\rho}\approx a$$. А если их нет? Если для a нет такого b, что $$a \stackrel{\rho}{\sim} b$$, то, очевидно, не $$a^{\rho}\approx a$$ (иначе мы бы взяли b = a).
Отсюда понятно, что наше бинарное отношение — это какое-то отношение эквивалентности, к которому присоединили такие элементы a, что для всех них не существует таких b, что $$a \stackrel{\rho}{\sim} b$$.
Тогда решение можно разбить на две части:
1. Посчитать количество отношений эквивалентности на множествах размеров 0, 1, ..., n - 1
2. Посчитать, сколькими способами туда можно добавить недостающие "пустые" элементы.
Отношение эквивалентности можно задать разбиением на классы эквивалентности.
Тогда первую часть задачи можно решить динамическим программированием: dp[elems][classes] — кол-во способов разбить elems первых элементов на classes классов эквивалентности. Переход — каждый элемент мы можем либо отнести в один из уже существующих классов, тогда их количество не изменится, либо же создать новый класс, тогда их количество увеличится на 1.
Вторая часть задачи. Зафиксируем m - размер множества, над которым мы посчитали количество отношений эквивалентности. Тогда нам нужно добавить к нему ещё n - m "пустых" элементов. Позиции для них можно выбрать C[n][n - m] способами, где C[n][k] — биномиальные коэффициенты. Их можно заранее посчитать треугольником Паскаля.
Тогда ответ — $$\sum_{m=0}^{n-1} C[n][n-m] \cdot eq[m]$$.
Сложность — O(n2)