Vahidlər

Gəlin n simvoldan ibarət olan bütün mümkün sıraları nəzərdən keçirək - sıfırlar və birlər (cəmi 2^n belə sıra mövcuddur). Bizim marağımızda olan, içərisində haradasa k ardıcıl birlərdən ibarət olan bir seqmentin olduğu sıralardır. Daha dəqiq desək, bizi belə sıraların sayı maraqlandırır. Bu say çox böyük ola bilər, buna görə də bu sayın 1000007-yə bölünməsindən qalanı tapmaq lazımdır.

Giriş məlumatları

İki təbii ədəd n və k (1 ≤ n ≤ 100000, 1 ≤ k ≤ 100).

Çıxış məlumatları

k ardıcıl birlərdən ibarət olan ən azı bir seqmentin olduğu sıraların sayının 1000007-yə bölünməsindən qalanı tapın.