CF568B.Symmetric and Transitive

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 , in this case we use a notation .

Binary relation is equivalence relation, if:

1. It is reflexive (for any a it is true that );
2. It is symmetric (for any a, b it is true that if , then );
3. It is transitive (if and , than ).

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 , then (according to property (2)), which means (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.

小约翰最近学习了集合论，现在他正在研究二元关系。你可能听说过“等价关系”这一术语。这类关系在数学的许多领域中都极为重要。例如，两个数相等的关系便是一种等价关系。

设 $ A $ 是某个集合，$ \rho $ 是由 $ A $ 中元素构成的有序对 $ (a,,b) $ 所组成的集合，则称 $ \rho $ 为集合 $ A $ 上的一个二元关系。对于集合 $ A $ 中的两个元素 $ a $ 和 $ b $，若有序对 属于 $ \rho $，则称 $ a $ 与 $ b $ 满足关系 $ \rho $；此时我们记作 。

若一个二元关系满足以下三条性质，则称其为等价关系：

1. 自反性（对任意 $ a $，均有 ）；
2. 对称性（对任意 $ a $、$ b $，若 ，则必有 ）；
3. 传递性（若 且 ，则必有 ）。

小约翰并非完全无知，他注意到第一条（自反性）条件其实并非必要！以下是他的“证明”：

任取两个元素 $ a $ 和 $ b $。若 ，则由性质（2）可得 ，再由性质（3）即得 。

这不是很简单吗？然而，你发现小约翰的“证明”是错误的，并决定向他展示大量反例来说明其错误。

你的任务是：计算在大小为 $ n $ 的集合上，满足对称性、传递性但不满足自反性（即不是等价关系）的二元关系的个数。

由于该数目可能非常大（根据小约翰的说法，它不为 0），请输出该数目对 $ 10^9 + 7 $ 取模的结果。

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

一行中包含一个整数 $n$（$1 \leq n \leq 4000$）。

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

在一行中输出该问题的答案对 $10^9 + 7$ 取模的结果。

If n = 1 there is only one such relation — an empty one, i.e. . In other words, for a single element x of set A the following is hold: .

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 , ρ = {(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.

当 $n = 1$ 时，仅存在一个这样的关系——即空关系，即 。换言之，对于集合 $A$ 中的唯一元素 $x$，以下关系成立：。

当 $n = 2$ 时，存在三个这样的关系。假设集合 $A$ 包含两个元素 $x$ 和 $y$。则所有合法的关系为：、$\rho = \{(x,\,x)\}$、$\rho = \{(y,\,y)\}$。容易看出，上述所列的三个二元关系均为对称且传递的关系，但它们都不是等价关系。