Khu vườn tăng dần
Đề bài
Mô tả
Thiên Sinh là một Người làm vườn Thiên giới trẻ tuổi và đầy tham vọng, được giao chăm sóc một hàng cây thần kỳ đặc biệt. Khu vườn của anh gồm cây xếp thành hàng, cây thứ có chiều cao ban đầu . Thẩm mỹ của Thiên giới đòi hỏi sự hoàn hảo, và một cuộc kiểm tra lớn sẽ diễn ra sau đúng ngày nữa.
Để chuẩn bị, Sinh có một công cụ mạnh mẽ: một bình tưới chứa Tinh chất Tăng trưởng Thần thánh. Mỗi ngày, anh thực hiện đúng một lần tưới. Một lần tưới gồm việc chọn một đoạn cây liên tiếp từ chỉ số đến (bao gồm cả hai đầu, ) và tưới chúng. Tinh chất mạnh đến mức mọi cây trong đoạn được chọn lập tức cao thêm đúng một đơn vị.
Để vượt qua cuộc kiểm tra, khu vườn phải thể hiện "Vẻ đẹp Tăng dần Hoàn hảo", nghĩa là chiều cao cuối cùng của các cây phải tăng ngặt. Tức là sau đúng ngày tưới, chiều cao cuối cùng phải thỏa mãn .
Thiên Sinh là người lập kế hoạch tỉ mỉ. Anh muốn biết tổng số "lịch tưới" khác nhau mà anh có thể thực hiện để đạt được vẻ đẹp này. Một lịch tưới là một dãy gồm lần tưới, mỗi ngày một lần. Hai lịch tưới được coi là khác nhau nếu ở một ngày nào đó, đoạn được chọn khác nhau.
Cho chiều cao ban đầu của các cây, hãy giúp Sinh tính số lịch tưới hợp lệ khác nhau. Vì đáp án có thể rất lớn, hãy in ra phần dư khi chia cho .
Dữ liệu vào
- Dòng đầu tiên gồm hai số nguyên và .
- Dòng thứ hai gồm số nguyên : chiều cao ban đầu của các cây.
Dữ liệu ra
In ra một số nguyên là số dãy lần tưới làm cho dãy tăng ngặt, lấy phần dư khi chia cho .
Ràng buộc
- ,
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 2 1 1 1 |
2 | Có hai lịch tưới hợp lệ: chọn ở ngày thứ nhất và ở ngày thứ hai; hoặc chọn ở ngày thứ nhất và ở ngày thứ hai. |
| 3 3 1 1 1 |
15 | |
| 5 5 10 9 9 9 10 |
590 |
Bình luận