题目描述

等价关系是满足自反性、对称性、传递性的关系，例如，两个数字的等式是等价关系。

集合 $A$ 中的元素组成的二元组 $(a, b)$ 称为集合 $A$ 上的二元关系。对于集合 $A$ 中的两个元素 $a$ 和 $b$，如果它们满足 $(a,b)\in \rho$，则称它们是属于关系 $ρ$ 的。

你的任务是计算一组大小为 $n$ 的二元关系的数量，使它们是对称的、可传递的，但不是等价关系（即它们不是自反的）。

答案对 $10^{9}+7$ 的取模。

输入格式

一个整数 $n$（$1\le n\le 4000$）。

输出格式

一个整数表示答案模 $10^{9}+7$。

1

1

如果 $n=1$，只有空关系满足要求。

2

3

如果 $n=2$，则有三个这样的关系。假设集合 $A$ 由两个元素组成，$x$ 和 $y$。$\rho = \varnothing$，$ρ={(x,x)}$，$ρ={(y,y)}$。很容易看出，列出的三个二元关系是对称和传递关系，但它们不是等价关系。

3

10