Ami chuẩn bị xây cầu thang có đúng n bậc thang. Cái cầu thang của Ami đương nhiên phải có những nét đặc biệt riêng. Đó là có thể tồn tại 2 bậc thang có độ cao bằng nhau. Tất nhiên, cái cầu thang này luôn đưa mọi người đi lên, hay nói cách khác, nếu dãy a₁,a₂,..,a_n là dãy chiều cao của bậc thang 1 , 2 ,... thì không tồn tại 2 chỉ số i < j và a_i > a_j. Thêm một điều đặc biệt nữa, đó là chiều cao của bậc thang luôn nhỏ hơn hoặc bằng một số tự nhiên k mà Ami mong muốn. Các bạn là những thợ xây lành nghề, hãy tính xem có bao nhiêu chiếc cầu thang thỏa mãn yêu cầu của Ami nhé. Vì kết quả có thể rất lớn, các bạn chỉ cần chia dư cho 10⁹+7.

Dữ liệu vào

Dòng đầu là 2 số nguyên dương n và k (n , k <= 10⁶).

Dữ liệu ra

Số cầu thang thỏa mãn yêu cầu sau khi đã chi dư cho 10⁹+7.