DHBB 2024 - CBH - 11 - Những viên bi

Xem dạng PDF

Gửi bài giải

Điểm: 50,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, PyPy, Python, Scratch, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Trên hệ trục tọa độ ~Oxy~, Bờm lần lượt đặt ~N~ viên bi, viên bi thứ ~i~ có tọa độ ~(0, i)~. Ở mỗi lượt chơi sau đây, Bờm có ba lựa chọn:

  • Không làm gì cả.

  • Chọn một viên bi, di chuyển lên trên ~1~ đơn vị, nếu viên bi ở vị trí ~(i, j)~, ta có thể đưa viên bi về vị trí ~(i + 1, j)~.

  • Chọn một viên bi, di chuyển xuống dưới ~1~ đơn vị, nếu viên bi ở vị trí ~(i, j)~, ta có thể đưa viên bi về vị trí ~(i - 1, j)~.

  • Sau ~K~ lượt chơi, ~N~ viên bi lần lượt kết thúc ở các tọa độ ~(x_1, 1), (x_2, 2), (x_3, 3), \dots, (x_N, N)~.

Yêu cầu: Đếm số cách đi khác nhau của Bờm modulo ~10^9 + 7~ để từ trạng thái ban đầu, sau ~K~ lượt đi, các viên bi ở trạng thái đích. Hai cách chơi được gọi là khác nhau nếu như tồn tại một lượt chơi mà thao tác ở cách chơi này khác thao tác ở cách chơi kia.

Input

  • Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ ~(1 \le N \le 100, 1 \le K \le 1000)~, lần lượt là số lượng viên bi và số lượt mà Bờm đã chơi.

  • Dòng tiếp theo gồm ~N~ số nguyên ~x_i~ ~(-1000 \le x_i \le 1000)~, số nguyên thứ ~i~ biểu diễn viên bi thứ ~i~ kết thúc ở tọa độ ~(x_i, i)~.

Output

In ra một số nguyên duy nhất là số cách di chuyển những viên bi MOD ~10^9 + 7~.

Scoring

Subtask Điểm Ràng buộc
1 ~25\%~ ~\sum_{i=1}^{N} \lvert x_i \rvert = K~
2 ~25\%~ ~N = 1~
3 ~50\%~ Không có giới hạn gì thêm

Sample Input 1

2 2
1 -1

Sample Output 1

2

Sample Input 2

5 20
1 2 3 4 5

Sample Output 2

182783854

Notes

Ở ví dụ 1: chúng ta có thể di chuyển viên bi ~1~ lên trên trên trước và di chuyển viên bi ~2~ xuống dưới sau, hoặc là di chuyển viên bi ~2~ xuống dưới trước và di chuyển viên bi ~1~ lên trên sau. Vì thế có hai cách để di chuyển viên bi về đúng vị trí.


Bình luận

Hãy đọc nội quy trước khi bình luận.


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