VMROPES - Các sợi dây
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Ở một vùng núi, người ta dùng những sợi dây để di chuyển qua những con suối. Một sợi dây đủ dài sẽ được dùng để vắt ngang giữa hai bờ suối. Sau đó, người ta sẽ đu dây để di chuyển từ đầu này sang đầu kia. Không phải lúc nào người ta cũng có thể dễ dàng tìm được một sợi dây thừng đủ dài. Vì vậy, trong một số trường hợp, người ta phải nối các đoạn dây thừng ngắn với nhau để tạo thành một đoạn dài.
Một số đẹp là một số mà trong biểu diễn thập phân của nó, hai chữ số cạnh nhau có chênh lệch không quá k đơn vị. Ví dụ khi k=1 thì 323321 là một số đẹp, còn 109899 thì không phải số đẹp. Một đoạn dây thừng có độ dài là số đẹp sẽ khiến cho dây thừng có được sự chắc chắn.
Bờm kinh doanh các đoạn dây thừng. Hiện tại, Bờm có rất nhiều đoạn dây thừng có độ dài là các số đẹp nằm trong khoảng từ A đến B. Bờm muốn tính xem có bao nhiêu cách để nối các đoạn dây thừng lại để tạo thành một đoạn dây vừa đủ để vắt qua con suối (có thể có các đoạn thừng có độ dài bằng nhau).
Biết k, A, B và khoảng cách giữa hai bờ suối, tính số cách để Bờm nối các sợi dây thừng để tạo thành một đoạn dây dài có độ dài bằng khoảng cách giữa hai bờ suối.
Input
Input gồm một dòng duy nhất chứa 4 số nguyên n, k, A, B (1 ≤ n ≤ 10 5 , 0 ≤ k ≤ 9, 1 ≤ A ≤ B ≤ n, B ≤ 95000), trong đó n là khoảng cách giữa hai bờ suối.
Output
In ra số cách để nối các đoạn dây trong mô đun 10 9 +7.
Giới hạn
20% số test có n ≤ 10000.
Sau khi kết thúc kỳ thi, kết quả của bạn là kết quả lần nộp bài cuối cùng
Example
Input:
3 0 1 2
Output:
3
Example
Input:
5 2 1 4
Output:
15
Example
Input:
10 3 2 10
Output:
34
- Người up: voj
- Nguồn bài: VM15 - Kiên