Company: Infosys_
Difficulty: medium
Beautiful strings Problem Description You are given two numbers N and K . A string is called beautiful if it satisfies the following conditions: Its length is exactly N . There is NO index i such that both S i and S i+1 are vowel letters. The number of indices i such that S i = S i+1 is exactly K . Find the total number of beautiful strings. Since the answer can be large, return it modulo 10 9 + 7 . Note The vowel letters are: {a, e, i, o, u} . Input Format The first line contains an integer, N , denoting the length of the beautiful string. The next line contains an integer, K , denoting the number of pairs of consecutive equal letters. Constraints 1 ≤ N ≤ 10 9 0 ≤ K ≤ 100 Example 1: Input: 2 0 Output: 630 Explanation: The explanation for this test case is not provided.