Đếm số cách xếp 2n viên bi lên bảng vuông kích thước n \times n sao cho mỗi hàng và mỗi cột có chính xác hai viên bi.
Input và Output
Input: (bàn phím
)
- Một dòng duy nhất gồm một số nguyên dương n (2 \le n \le 10^9).
Output: (màn hình
)
- Một dòng duy nhất gồm số cách xếp. Vì kết quả có thể rất lớn nên chỉ cần in ra phần dư của kết quả sau khi chia cho 10^9 + 7.
Sample 1
Input (bàn phím
)
2
Output (màn hình
)
1
Note
- Chỉ có một cách xếp duy nhất là xếp 4 viên bi vào 4 ô trên bàn cờ.
Sample 2
Input (bàn phím
)
3
Output (màn hình
)
6
Note
- Gọi ((1, a), (2, b), (3, c)) là các ô không được xếp bi. Do a, b, c đôi một phân biệt nên có 3! = 6 cách chọn tương ứng với 6 cách xếp bi.
Bình luận