Divisor Sequences
Национална Олимпиада по Информатика 2013, Кръг 3
Time Limit: 0.1s, Memory Limit: 64MiB
Ели иска да състави редица от цели числа с N елемента (A1, A2, ..., AN), за която е изпълнено:
  • всяко от числата е между 1 и K, включително;
  • или Ai се дели на Ai+1, или Ai+1 се дели на Ai за 1 ≤ i < N.
Напишете програма, която намира колко на брой такива редици може да състави Ели.
Вход
На единствен ред на стандартния вход ще бъдат зададени двете цели числа N и K – съответно дължината на исканите редици и максималната стойност на всеки техен елемент.
Изход
На единствен ред на стандартния изход изведете едно цяло число – броя редици, които може да състави Ели. Тъй като това число може да е много голямо, вместо самото число, изпечатайте единствено неговия остатък при деление на 1,000,000,007.
Ограничения
  • 1 ≤ N, K ≤ 1000
Примерен Вход Примерен Изход
2 4 12
4 6 362
711 42 402398970
Възможните редици в първия пример са (1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 4), (3, 1), (3, 3), (4, 1), (4, 2) и (4, 4). Във втория пример някои от възможните редици са (1, 1, 1, 1), (4, 2, 4, 2), (6, 2, 4, 1), (1, 2, 4, 4), (1, 1, 2, 1).
Мрън!