Đa giác phức tạp
Đề bài
Mô tả
Vào một ngày đẹp trời ở công viên Đầm Sen, anh Đôn cầm một túi que với nhiều độ dài khác nhau. Anh nhận ra rằng với những que này, một số que có thể ghép lại thành những đa giác thú vị, còn một số thì không.
Ví dụ, anh Đôn có ba que trong túi với độ dài lần lượt là , và . Anh biết rằng với ba que này, anh có thể xếp thành một tam giác đẹp. Tuy nhiên, hôm trước, khi anh Đôn có bốn que với độ dài , , và , anh biết không có cách nào xếp chúng thành một tứ giác hợp lệ.
Nhiệm vụ của bạn: giúp anh Đôn tính số cách khác nhau để chọn các que từ túi tạo thành các đa giác khác nhau. Hai đa giác được coi là khác nhau nếu có ít nhất một que được dùng trong đa giác này mà không có trong đa giác kia, và ngược lại.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên (): số que trong túi của anh Đôn.
Dòng thứ hai chứa số nguyên (): độ dài của que tương ứng.
Dữ liệu ra
In ra một số nguyên là số đa giác khác nhau có thể tạo được, lấy modulo .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 2 2 2 2 |
5 | Có tam giác với các cạnh và tứ giác với các cạnh . |
| 5 1 2 3 4 5 |
9 | Có đa giác: , , , , , , , , . |
Bình luận