小约翰尼最近学习了集合论。现在他正在研究二元关系。您可能听说过“等价关系”这个术语。这些关系在数学的许多领域都非常重要。例如,两个数相等就是等价关系。
某个集合 A 的元素对 (a, b) 组成的集合 ρ 被称为集合 A 上的二元关系。对于集合 A 的两个元素 a 和 b,我们说它们处于关系 ρ 中,如果对 $$(a,b)\in\rho$$,在这种情况下我们使用符号 $$a \stackrel{\rho}{\sim} b$$。
二元关系是等价关系,如果:
1. 它是自反的(对于任何 a 来说 $$a^{\rho}\approx a$$ 都是正确的);
2. 它是对称的(对于任何 a, b,如果 $$a \stackrel{\rho}{\sim} b$$,则 $$b \stackrel{\rho}{\sim} a$$ 成立);
3. 它是及物性的(如果 $$a \stackrel{\rho}{\sim} b$$ 和 $$b \sim c$$,则大于 $$a \stackrel{\rho}{\sim} c$$)。
小约翰尼并不完全是个傻瓜,他注意到第一个条件不是必需的!这是他的“证明”:
取任意两个元素,a 和 b。如果$$a \stackrel{\rho}{\sim} b$$,则$$b \stackrel{\rho}{\sim} a$$(根据性质(2)),这意味着$$a^{\rho}\approx a$$(根据性质(3))。
很简单,不是吗?然而,您注意到约翰尼的“证明”是错误的,并决定向他展示很多证明他错误的例子。
这是你的任务:计算一组大小为 n 的二元关系的数量,使得它们是对称的、传递的,但不是等价关系(即它们不是自反的)。
由于它们的数字可能非常大(根据小约翰尼的说法,不是 0),因此打印该数字除以 109 + 7 的余数。
输入
单行包含一个整数 n (1 ≤ n ≤ 4000)。
输出
在一行中打印出模 109 + 7 的问题答案。
示例
输入 #1
1
输出 #1
1
输入 #2
2
输出 #2
3
输入 #3
3
输出 #3
10
注意
如果 n = 1,则只有一种这样的关系——空关系,即 $$\varphi=\emptyset$$。换句话说,对于集合 A 的单个元素 x,以下成立:$$x^{\rho}x^{r}$$。
如果 n = 2,则存在三个这样的关系。假设集合 A 由两个元素 x 和 y 组成。那么有效关系是 $$\varphi=\emptyset$$, ρ = {(x, x)}, ρ = {(y, y)}。容易看出,所列出的三个二元关系是对称且传递的关系,但它们不是等价关系。