Design Patterns
Дизайн и Анализ на Алгоритми, 2011
Time Limit: 0.2s, Memory Limit: 64MiB
Design Patterns (съкратено DP) е важна част от програмирането, която Ели иска да научи. За нещастие, момичето наскоро попадна на статия за DP, в чиято достоверност Ели има известни съмнения. Както е казал Ейбрахам Линкълн, "Не винаги може да се вярва в достоверността на цитатите в Интернет".
Статията твърдеше, че един код с N символа е добре написан, ако не съдържа повече от K последователни гласни. За гласни считаме буквите от английската азбука {'a', 'e', 'o', 'u', 'i', 'y'}. Ели се чуди колко на брой стринга, съставени от точно N малки латински букви, съществуват, така че да не съдържат повече от K последователни гласни.
Статията твърдеше, че един код с N символа е добре написан, ако не съдържа повече от K последователни гласни. За гласни считаме буквите от английската азбука {'a', 'e', 'o', 'u', 'i', 'y'}. Ели се чуди колко на брой стринга, съставени от точно N малки латински букви, съществуват, така че да не съдържат повече от K последователни гласни.
Вход
На единствен ред на стандартния вход ще бъдат зададени две цели числа N и K.
Изход
На единствен ред на стандартния изход изведете едно цяло число – отговора на задачата. Тъй като това число може да е много голямо, изведете само остатъка му при деление на 1,000,000,007.
Ограничения
- 1 ≤ N, K ≤ 1,000
| Примерен Вход | Примерен Изход |
|---|---|
| 3 1 | 15920 |
| 5 2 | 11510720 |
| 666 42 | 9515787 |
В първия пример отговорът е броят на всички стрингове с дължина три (263) минус броя на стринговете, които имат поне две последователни гласни (62 * 26 + 26 * 62 - 63).