CF568B Symmetric and Transitive

小约翰最近学习了集合论。现在他正在研究二元关系。你可能听说过“等价关系”这个术语。这类关系在许多数学领域都非常重要。例如，两个数的相等关系就是一种等价关系。 设 $ρ$ 是集合 $A$ 上元素对 $(a, b)$ 的集合，则 $ρ$ 称为集合 $A$ 上的一个二元关系。对集合 $A$ 的两个元素 $a$ 和 $b$，如果对 $(a, b)$ 属于 $ρ$，则称 $a$ 与 $b$ 关于关系 $ρ$ 相关，此时我们记做 $a \; ρ \; b$。 二元关系是等价关系，当且仅当： 1. 它是自反的（对于任意 $a$，都有 $a \; ρ \; a$ 成立）； 2. 它是对称的（对任意 $a$，$b$，如果 $a \; ρ \; b$，则 $b \; ρ \; a$ 也成立）； 3. 它是传递的（如果 $a \; ρ \; b$ 且 $b \; ρ \; c$，那么 $a \; ρ \; c$ 也成立）。 但小约翰并不傻，他注意到第一个条件或许不是必要的，这里是他的“证明”： 取任意两个元素 $a$ 和 $b$，如果 $a \; ρ \; b$，那么 $b \; ρ \; a$（由性质（2）），这意味着 $a \; ρ \; a$（由性质（3））。 这很简单，对吧？然而，你注意到小约翰的“证明”是错误的，便决定给他展示很多反例来反驳他的结论。 你的任务如下：计算集合大小为 $n$ 的集合上满足对称性和传递性的二元关系的个数，这些关系不是等价关系（也就是说不是自反的）。 由于关系总数可能非常大（小约翰认为不是 0），所以请输出结果对 $10^9+7$ 取模后所得的余数。

一行包含一个整数 $n$，$1 \leq n \leq 4000$。

输出一个整数，表示所求的数量对 $10^9+7$ 取模后的结果。

如果 $n=1$，此时只有一种关系——即空关系，也就是 $ρ = \varnothing$。换句话说，对于集合 $A$ 的唯一一个元素 $x$，有 $x$ 不与自己相关，即 $x \not\; ρ\; x$。 如果 $n=2$，则共有三种关系。假设集合 $A$ 包含 $x,y$ 两个元素，则符合条件的关系为 $ρ = \varnothing$，$ρ = \{(x,x)\}$，$ρ = \{(y,y)\}$。可以看到这三种二元关系都是对称且传递的，但都不是等价关系。 由 ChatGPT 5 翻译