Number of distinct words of size N with at most K contiguous vowels | Power function to calculate long powers with mod ; Function for finding number of ways to create string with length N and atmost K contiguous vowels ; Array dp to store number of ways ; dp [ i ] [ 0 ] = ( dp [ i - 1 ] [ 0 ] + dp [ i - 1 ] [ 1 ] . . dp [ i - 1 ] [ k ] ) * 21 ; Now setting sum to be dp [ i ] [ 0 ] ; If j > i , no ways are possible to create a string with length i and vowel j ; If j = i all the character should be vowel ; dp [ i ] [ j ] relation with dp [ i - 1 ] [ j - 1 ] ; Adding dp [ i ] [ j ] in the sum ; Driver Code ; Input ; Function Call
def power ( x , y , p ) : NEW_LINE INDENT res = 1 NEW_LINE x = x % p NEW_LINE if ( x == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT while ( y > 0 ) : NEW_LINE INDENT if ( y & 1 ) : NEW_LINE INDENT res = ( res * x ) % p NEW_LINE DEDENT y = y >> 1 NEW_LINE x = ( x * x ) % p NEW_LINE DEDENT return res NEW_LINE DEDENT def kvowelwords ( N , K ) : NEW_LINE INDENT i , j = 0 , 0 NEW_LINE MOD = 1000000007 NEW_LINE dp = [ [ 0 for i in range ( K + 1 ) ] for i in range ( N + 1 ) ] NEW_LINE sum = 1 NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] = sum * 21 NEW_LINE dp [ i ] [ 0 ] %= MOD NEW_LINE sum = dp [ i ] [ 0 ] NEW_LINE for j in range ( 1 , K + 1 ) : NEW_LINE INDENT if ( j > i ) : NEW_LINE INDENT dp [ i ] [ j ] = 0 NEW_LINE DEDENT elif ( j == i ) : NEW_LINE INDENT dp [ i ] [ j ] = power ( 5 , i , MOD ) NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j - 1 ] * 5 NEW_LINE DEDENT dp [ i ] [ j ] %= MOD NEW_LINE sum += dp [ i ] [ j ] NEW_LINE sum %= MOD NEW_LINE DEDENT DEDENT return sum NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 3 NEW_LINE K = 3 NEW_LINE print ( kvowelwords ( N , K ) ) NEW_LINE DEDENT