Bạn muốn tìm hiểu có bao nhiêu cách đi lên một cầu thang. Cầu thang gồm \(N\) bậc; độ chênh cao của bậc thứ \(k\) là \(h_k\) mm, với \(1 \le k \le N\).

Trong một lần bước, bạn có thể đi lên một hoặc nhiều bậc có tổng độ chênh cao không vượt quá \(P\) mm. Khi đi lên cầu thang, bạn không giậm chân tại chỗ trên cùng một bậc và không đi xuống. Hai cách đi lên được xem là giống nhau nếu các bậc được đặt chân lên là giống nhau.

Yêu cầu

Hãy tính số cách đi lên hết cầu thang, lấy phần dư khi chia cho \(1\,234\,567\).

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(P\), cách nhau bởi dấu cách.
• Dòng thứ \(k\) trong \(N\) dòng tiếp theo chứa số nguyên \(h_k\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa một số nguyên: phần dư của số cách đi lên cầu thang khi chia cho \(1\,234\,567\).

Ràng buộc

• Giới hạn trong kỳ thi gốc: thời gian \(1{,}5\) giây, bộ nhớ \(64\) MB.

• \(1 \le N \le 500\,000\): số bậc của cầu thang.

• \(1 \le P \le 500\,000\,000\): tổng độ chênh cao tối đa có thể vượt qua trong một lần bước, tính bằng mm.
• \(1 \le h_k\) với mọi \(1 \le k \le N\): độ chênh cao của bậc thứ \(k\), tính bằng mm.

Tổng độ chênh cao của các bậc thỏa mãn:

Phân nhóm

Bài này có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm.

• Các bộ kiểm thử có tổng cộng \(50\) điểm thỏa mãn \(N \le 3\,000\).

Ví dụ

6 350
315
191
98
70
126
200

9