Count of Distinct strings possible by inserting K characters in the original string | JavaScript 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
var mod = 10007 ; function binExp ( base , power ) { var x = 1 ; while ( power != 0 ) { if ( power % 2 == 1 ) x = ( ( ( x % mod ) * ( base % mod ) ) % mod ) ; base = ( ( ( base % mod ) * ( base % mod ) ) % mod ) ; power = parseInt ( power / 2 ) ; } return x ; } function fact ( num ) { var result = 1 ; for ( var i = 1 ; i <= num ; ++ i ) { result = ( ( ( result % mod ) * ( i % mod ) ) % mod ) ; } return result ; } function calculate_nCi ( N , i ) { var nfact = fact ( N ) ; var ifact = fact ( i ) ; var dfact = fact ( N - i ) ; var inv_ifact = binExp ( ifact , mod - 2 ) ; var inv_dfact = binExp ( dfact , mod - 2 ) ; var denm = ( ( ( inv_ifact % mod ) * ( inv_dfact % mod ) ) % mod ) ; var answer = ( ( ( nfact % mod ) * ( denm % mod ) ) % mod ) ; return answer ; } function countSubstring ( N , s , k ) { var allWays = binExp ( 26 , N ) ; var noWays = 0 ; for ( var i = 0 ; i < s ; ++ i ) { var nCi = calculate_nCi ( N , i ) ; var remaining = binExp ( 25 , N - i ) ; var multiply = ( ( ( nCi % mod ) * ( remaining % mod ) ) % mod ) ; noWays = ( ( ( noWays % mod ) + ( multiply % mod ) ) % mod ) ; } var answer = ( ( ( allWays % mod ) - ( noWays % mod ) ) % mod ) ; if ( answer < 0 ) answer += mod ; document . write ( answer ) ; } var str = " " ; var k = 2 ; var s = str . length ; var N = s + k ; countSubstring ( N , s , k ) ;