Counting cool words P67933


Statement
 

pdf   zip

thehtml

In this problems, we say that a word is cool if it does not have two consecutive consonants. Write a program to compute how many words with n lowercase letters, v of which are vowels, are cool.

For instance, these are some of the many cool words for n = 5 and v = 3:

aabab ⁠ ⁠ababa ⁠ ⁠babaa ⁠ ⁠toiep ⁠ ⁠zeyui

Remember that there are 5 vowels and 21 consonants.

Input

Input consists of several cases, each with two natural numbers 1 ≤ n ≤ 15 and 0 ≤ vn.

Output

For every case, print the number of cool words with n lowercase letters, v of which are vowels. This number is always smaller than 1018.

Public test cases
  • Input

    1 0
    1 1
    2 0
    2 1
    2 2
    3 0
    3 1
    3 2
    3 3
    5 3
    15 9
    15 6
    15 15
    

    Output

    21
    5
    0
    210
    25
    0
    2205
    1575
    125
    330750
    35177510566406250
    0
    30517578125
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++