Музейні маршрути

Нещодавно відкрився престижний інтерактивний музей з унікальною системою відвідування. У музеї використовується програма цифрових пропусків, розроблена для того, щоб заохочувати ретельне вивчення експозицій та керувати потоком відвідувачів.

Кожен відвідувач при вході отримує спеціальний цифровий музейний пропуск. Пропуск входить у вартість квитка та відстежує прогрес відвідувача по музею за допомогою електронної системи штампів.

Щоб відвідувачі взаємодіяли з експозиціями осмислено, а не поспішали, музей впровадив структуровану систему екскурсій. Музей складається з $N$ виставкових залів, і в кожному залі відвідувачі повинні відсканувати свій цифровий пропуск на станції перевірки, що додає цифровий штамп до їхнього запису. Як тільки відвідувач накопичить більше $K$ штампів, його автоматично направляють до виходу, і він отримує сертифікат про завершення екскурсії. Якщо штампів менше $K$, він може вибрати будь-який з'єднувальний коридор з поточного залу до іншого залу і продовжити екскурсію. У новому залі він знову повинен відсканувати свій пропуск. Система вимагає, щоб відвідувачі не могли залишити музей, доки не зберуть рівно $K$ штампів на своєму пропуску.

Юний ентузіаст музеїв Віктор планує свій візит і хоче дослідити найбільш цікаві маршрути по музею. Однак спочатку йому потрібно визначити загальну кількість можливих маршрутів екскурсії. Оскільки це число може бути досить великим, він просить вас обчислити результат за модулем $1000000007$.

Допоможіть йому знайти рішення.