Count of Distinct strings possible by inserting K characters in the original string | Python3 program for the above approach ; Function to calculate and return x ^ n in log ( n ) time using Binary Exponentiation ; Function to calculate the factorial of a number ; Function to calculate combination ; nCi = ( n ! ) / ( ( n - i ) ! * i ! ) ; Using Euler 's theorem of Modular  multiplicative inverse to find  the inverse of a number.  (1/a)%mod=a^(m?2)%mod ; Function to find the count of possible strings ; Number of ways to form all possible strings ; Number of ways to form strings that don 't contain the input  string as a subsequence ; Checking for all prefix length from 0 to | S | - 1. ; To calculate nCi ; Select the remaining characters 25 ^ ( N - i ) ; Add the answer for this prefix length to the final answer ; Answer is the difference of allWays and noWays ; Print the answer ; Driver Code
mod = 1000000007 NEW_LINE def binExp ( base , power ) : NEW_LINE INDENT x = 1 NEW_LINE while ( power ) : NEW_LINE INDENT if ( power % 2 == 1 ) : NEW_LINE INDENT x = ( ( ( x % mod ) * ( base % mod ) ) % mod ) NEW_LINE DEDENT base = ( ( ( base % mod ) * ( base % mod ) ) % mod ) NEW_LINE power = power // 2 NEW_LINE DEDENT return x NEW_LINE DEDENT def fact ( num ) : NEW_LINE INDENT result = 1 NEW_LINE for i in range ( 1 , num + 1 ) : NEW_LINE INDENT result = ( ( ( result % mod ) * ( i % mod ) ) % mod ) NEW_LINE DEDENT return result NEW_LINE DEDENT def calculate_nCi ( N , i ) : NEW_LINE INDENT nfact = fact ( N ) NEW_LINE ifact = fact ( i ) NEW_LINE dfact = fact ( N - i ) NEW_LINE inv_ifact = binExp ( ifact , mod - 2 ) NEW_LINE inv_dfact = binExp ( dfact , mod - 2 ) NEW_LINE denm = ( ( ( inv_ifact % mod ) * ( inv_dfact % mod ) ) % mod ) NEW_LINE answer = ( ( ( nfact % mod ) * ( denm % mod ) ) % mod ) NEW_LINE return answer NEW_LINE DEDENT def countSubstring ( N , s , k ) : NEW_LINE INDENT allWays = binExp ( 26 , N ) NEW_LINE noWays = 0 NEW_LINE for i in range ( s ) : NEW_LINE INDENT nCi = calculate_nCi ( N , i ) NEW_LINE remaining = binExp ( 25 , N - i ) NEW_LINE multiply = ( ( ( nCi % mod ) * ( remaining % mod ) ) % mod ) NEW_LINE noWays = ( ( ( noWays % mod ) + ( multiply % mod ) ) % mod ) NEW_LINE DEDENT answer = ( ( ( allWays % mod ) - ( noWays % mod ) ) % mod ) NEW_LINE if ( answer < 0 ) : NEW_LINE INDENT answer += mod NEW_LINE DEDENT print ( answer ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT st = " abc " NEW_LINE k = 2 NEW_LINE s = len ( st ) NEW_LINE N = s + k NEW_LINE countSubstring ( N , s , k ) NEW_LINE DEDENT