Problem Brief

String Patterns (Also for Core/Database Intern :)

INTERNOA

See Snowflake online assessment and hiring insights

Given the length of a word (wordLen) and the maximum number of consecutive vowels that it can contain (maxVowels), determine how many unique words can be generated. Words will consist of English alphabetic letters a through z only. Vowels are a, e, i, o, u; consonants are the remaining 21 letters. In the explanations, v and c represent vowels and consonants.

Function Description

Complete the function calculateWays in the editor below.

calculateWays has the following parameters:

1. int wordLen: the length of a word
2. int maxVowels: the maximum number of consecutive vowels allowed in a word

Returns

int: the number of well-formed strings that can be created, modulo 1000000007(10⁹+7)

The result may be very large number, so return the answer modulo (10⁹ + 7).

Note:

While the answers will be within the limit of a 32 bit integer, interim values may exceed that limit. Within the function, you may need to use a 64 bit integer type to store them.

1Example 1

Input

wordLen = 1, maxVowels = 1

Output

Explanation

Patterns: {v, c} That means there are 26 possibilities, one for each letter in the alphabet.

2Example 2

Input

wordLen = 4, maxVowels = 1

Output

412776

Explanation

Patterns: {cccc, vccc, cvcc, ccvc, cccv, cvcv, ccvv, vcvv, vvcc, vvcv} There are 412,776 possibilities - see above 👆: (21 * 21 * 21 * 21) = 194481 (5 * 21 * 21 * 21) + (21 * 5 * 21 * 21) + (21 * 21 * 5 * 21) + (21 * 21 * 21 * 5) = 4 * 46305 = 185220 (5 * 21 * 5 * 21) + (21 * 5 * 21 * 5) + (5 * 21 * 21 * 5) = 3 * 11025 = 33075 194481 + 185220 + 33075 = 412776 possible solutions.

3Example 3

Input

wordLen = 4, maxVowels = 2

Output

451101

Explanation

In this case, all of the combinations from the previous example are still valid. - There are 5 additional patterns to consider, three with 2 vowels (vvcc, cvvc, ccvv) and 2 with 3 vowels (vvcv and vcvv). - Their counts are 3 * (5 * 5 * 21 * 21) = 3 * 11025 = 33075 and 2 * (5 * 5 * 5 * 21) = 2 * 2625 = 5250. - The total number of combinations then is 412776 + 33075 + 5250 = 451101.

Constraints

Limits and guarantees your solution can rely on.

1 ≤ wordLen ≤ 2500
0 ≤ maxVowels ≤ n