Design Patterns
Дизайн и Анализ на Алгоритми, 2011
Time Limit: 0.1s, Memory Limit: 64MiB
Design Patterns (съкратено DP) е важна част от програмирането, която Ели иска да научи. За нещастие, момичето наскоро попадна на статия за DP, в чиято достоверност Ели има известни съмнения. Както е казал Ейбрахам Линкълн, "Не винаги може да се вярва в достоверността на цитатите в Интернет".

Статията твърдеше, че един код с N символа е добре написан, ако не съдържа повече от K последователни гласни. За гласни считаме буквите от английската азбука {'a', 'e', 'o', 'u', 'i', 'y'}. Ели се чуди колко на брой стринга, съставени от точно N малки латински букви, съществуват, така че да не съдържат повече от K последователни гласни.
Вход
На единствен ред на стандартния вход ще бъдат зададени две цели числа N и K.
Изход
На единствен ред на стандартния изход изведете едно цяло число – отговора на задачата. Тъй като това число може да е много голямо, изведете само остатъка му при деление на 1,000,000,007.
Ограничения
  • 1 ≤ N, K ≤ 1,000
Примерен Вход Примерен Изход
3 115920
5 211510720
666 429515787
В първия пример отговорът е броят на всички стрингове с дължина три (263) минус броя на стринговете, които имат поне две последователни гласни (62 * 26 + 26 * 62 - 63).
Мрън!