Giải bài trực tuyến

Ở 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⁵, 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⁹+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