Hədiyyə

Karev sadə ardıcıllıqları, ən çox K elementdən ibarət olanları çox sevir. Uzunluğu K olan sadə ardıcıllıq, 0-dan K-1-ə qədər olan ədədlərlə bu sırada formalaşan ardıcıllıqdır. Məsələn, sadə ardıcıllıqlar {0}, {0,1,2,3}, {0,1,2,3,4,5,6}-dır, lakin {1}, {0,1,3,2}, {0,1,3} ardıcıllıqlar sadə deyildir.

Karevin ad günü yaxınlaşdığı üçün Polly ona bir neçə sadə ardıcıllıq alıb maraqlı bir ardıcıllıq yaratmaq istəyir. Maraqlı ardıcıllıq, hər biri ən çox K uzunluğunda olan bir neçə sadə ardıcıllığın birləşməsi ilə formalaşan ardıcıllıqdır. Məsələn, K = 3 olsun. Onda {0,1,2,0}, {0,1,0,1}, {0,0,0} və {0,1,2} maraqlı ardıcıllıqlardır, lakin {0,1,2,3}, {0,1,1} və {0,0,2} maraqlı deyildir.

Polly bir çox ardıcıllıq seçə biləcəyi üçün hansını seçəcəyini düşünür. İndi o, həqiqətən neçə seçim imkanı olduğunu merak edir. Karev Polly-nin çox yaxşı dostudur, buna görə də ona həqiqətən böyük bir hədiyyə almağa qərar verə bilər.

Polly-yə kömək etmək üçün aşağıdakı problemi həll edəcək bir proqram yazın: Verilən K – Polly-nin ala biləcəyi sadə ardıcıllıqların maksimum uzunluğu və N – yaratmaq istədiyi maraqlı ardıcıllığın uzunluğu, Polly-nin neçə fərqli maraqlı ardıcıllıq yarada biləcəyini hesablayın. Bu ədəd çox böyük ola biləcəyi üçün, nəticəni 10^9+7 modulu ilə çıxarın.

Giriş

Standart girişin birinci sətrində boşluqla ayrılmış iki ədəd verilir – N və K(1 ≤ K ≤ N ≤ 2000000 ).

Çıxış

Standart çıxışın birinci sətrində bir ədəd çıxarmalısınız – Polly-nin mövcud məhdudiyyətlərlə edə biləcəyi fərqli maraqlı ardıcıllıqların sayı. Cavabı 10^9+7 modulu ilə çıxarın.

Birinci nümunə üçün izah

K = 3 və N = 4 olsun. Mümkün maraqlı ardıcıllıqlar {0,0,0,0}; {0,0,0,1}; {0,0,1,0}; {0,0,1,2}; {0,1,0,0}; {0,1,0,1}; {0,1,2,0}-dır. Beləliklə, 7 ardıcıllıq var və bu, bu nümunə üçün cavabdır.