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

Điểm: 6,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

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

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

Phản xạ nếu với mọi $a \in A$ ta có $a ρ a$ .
Đối xứng nếu $a ρ b$ kéo theo $b ρ a$ .
Bắc cầu nếu $a ρ b$ và $b ρ c$ kéo theo $a ρ 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 \leq n \leq 4000$ .

Ví dụ

Input	Output	Giải thích
1	1	Có duy nhất quan hệ rỗng thoả mãn.
2	3	Với $A = {x, y}$ , ba quan hệ thoả mãn là $\emptyset$ , ${(x, x)}$ và ${(y, y)}$ .
3	10	Có $10$ quan hệ đối xứng, bắc cầu nhưng không phản xạ trên tập ba phần tử.

Bình luận

Không có bình luận tại thời điểm này.