Cắt bánh pizza
Đề bài
Mô tả
Alex có một chiếc bánh pizza muốn chia cho các bạn. Chiếc bánh có dạng một đa giác lồi cạnh. Alex quyết định cắt bánh theo tất cả các đường chéo của đa giác.
Sau khi cắt xong, hãy đếm tổng số miếng bánh thu được. Vì đáp án có thể rất lớn, hãy in ra đáp án theo modulo .
Biết rằng không có ba đường chéo nào của đa giác cắt nhau tại cùng một điểm.
Dữ liệu vào
Một dòng duy nhất chứa số nguyên dương ().
Dữ liệu ra
In ra số miếng bánh, theo modulo .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 | 4 | Hai đường chéo của tứ giác cắt nhau tại một điểm, chia bánh thành miếng. |
| 6 | 25 | Lục giác có đường chéo và giao điểm giữa chúng, cho miếng bánh. |
Bình luận