Quan hệ đối xứng và bắc cầu

Cho tập $A$ có $n$ phần tử. Một quan hệ hai ngôi $\rho$ trên $A$ là một tập con của $A\times A$. Ta viết $a\rho b$ khi $(a,b)\in \rho$.

Quan hệ $\rho$ được gọi là:

• Phản xạ nếu với mọi $a\in A$ ta có $a\rho a$.
• Đối xứng nếu $a\rho b$ kéo theo $b\rho a$.
• Bắc cầu nếu $a\rho b$ và $b\rho c$ kéo theo $a\rho c$.

Quan hệ được gọi là quan hệ tương đương nếu nó đồng thời phản xạ, đối xứng và bắc cầu.

Hãy đếm số quan hệ hai ngôi trên $A$ vừa đối xứng, vừa bắc cầu, nhưng không phải quan hệ tương đương (tức là không phản xạ). Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

Một dòng duy nhất chứa một số nguyên $n$.

Dữ liệu ra

In ra một dòng duy nhất là đáp số modulo ${10}^9+7$.

Ràng buộc

• $1\le n\le 4000$.

Ví dụ