Count of Distinct strings possible by inserting K characters in the original string | Java 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
class GFG { static final long mod = 1000000007 ; static long binExp ( long base , long power ) { long x = 1 ; while ( power != 0 ) { if ( power % 2 == 1 ) x = ( ( x % mod ) * ( base % mod ) ) % mod ; base = ( ( base % mod ) * ( base % mod ) ) % mod ; power = power / 2 ; } return x ; } static long fact ( long num ) { long result = 1 ; for ( long i = 1 ; i <= num ; ++ i ) { result = ( ( result % mod ) * ( i % mod ) ) % mod ; } return result ; } static long calculate_nCi ( long N , long i ) { long nfact = fact ( N ) ; long ifact = fact ( i ) ; long dfact = fact ( N - i ) ; long inv_ifact = binExp ( ifact , mod - 2 ) ; long inv_dfact = binExp ( dfact , mod - 2 ) ; long denm = ( ( inv_ifact % mod ) * ( inv_dfact % mod ) ) % mod ; long answer = ( ( nfact % mod ) * ( denm % mod ) ) % mod ; return answer ; } static void countSubstring ( long N , long s , long k ) { long allWays = binExp ( 26 , N ) ; long noWays = 0 ; for ( long i = 0 ; i < s ; ++ i ) { long nCi = calculate_nCi ( N , i ) ; long remaining = binExp ( 25 , N - i ) ; long multiply = ( ( nCi % mod ) * ( remaining % mod ) ) % mod ; noWays = ( ( noWays % mod ) + ( multiply % mod ) ) % mod ; } long answer = ( ( allWays % mod ) - ( noWays % mod ) ) % mod ; if ( answer < 0 ) answer += mod ; System . out . println ( answer ) ; } public static void main ( String [ ] args ) { String str = " abc " ; long k = 2 ; long s = str . length ( ) ; long N = s + k ; countSubstring ( N , s , k ) ; } }