Подарунок#8750
Кареву дуже подобаються прості послідовності, що складаються з не більше ніж чисел. Проста послідовність довжини — це послідовність, утворена числами від до K-1 у цьому порядку. Наприклад, прості послідовності — це , \{0,1,2,3\}, \{0,1,2,3,4,5,6\}, тоді як послідовності , \{0,1,3,2\}, \{0,1,3\} — не є такими.
Оскільки наближається день народження Карева, Поллі хотіла б купити для нього кілька простих послідовностей і об'єднати їх в цікаву послідовність. Цікава послідовність — це послідовність, утворена шляхом конкатенації кількох простих послідовностей, кожна з яких має довжину не більше . Наприклад, нехай K = 3. Тоді \{0,1,2,0\}, \{0,1,0,1\}, \{0,0,0\} і \{0,1,2\} є цікавими послідовностями, але \{0,1,2,3\}, \{0,1,1\} і \{0,0,2\} — ні.
Оскільки Поллі може вибрати багато послідовностей, вона замислюється, яку саме обрати. Тепер їй цікаво, скільки варіантів у неї є насправді. Карев — дуже хороший друг Поллі, тому вона може вирішити купити для нього дійсно великий подарунок.
Напишіть програму, щоб допомогти Поллі, вирішивши наступну задачу: враховуючи — максимальну довжину простих послідовностей, які Поллі може купити, і — довжину цікавої послідовності, яку вона хоче сформувати, обчисліть, скільки різних цікавих послідовностей вона може скласти. Оскільки це число може бути дуже великим, виведіть його за модулем 10^9+7.
На першому рядку стандартного вводу дано два числа, розділені пробілом — і (1 \leq K \leq N \leq 2000000).
Ви повинні вивести одне число на першому рядку стандартного виводу — кількість різних цікавих послідовностей, які Поллі може скласти за даних умов. Виведіть відповідь за модулем 10^9+7.
Приклад 1
Приклад 2
Приклад 3
Нехай K=3 і N=4. Можливі цікаві послідовності — це \{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\}. Отже, є послідовностей, і це є відповіддю для цього прикладу.