Count of Distinct strings possible by inserting K characters in the original string | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define int  long long int NEW_LINE const int mod = 1e9 + 7 ; int binExp ( int base , int power ) { int x = 1 ; while ( power ) { if ( power % 2 == 1 ) x = ( ( x % mod ) * ( base % mod ) ) % mod ; base = ( ( base % mod ) * ( base % mod ) ) % mod ; power = power / 2 ; } return x ; } int fact ( int num ) { int result = 1 ; for ( int i = 1 ; i <= num ; ++ i ) { result = ( ( result % mod ) * ( i % mod ) ) % mod ; } return result ; } int calculate_nCi ( int N , int i ) { int nfact = fact ( N ) ; int ifact = fact ( i ) ; int dfact = fact ( N - i ) ; int inv_ifact = binExp ( ifact , mod - 2 ) ; int inv_dfact = binExp ( dfact , mod - 2 ) ; int denm = ( ( inv_ifact % mod ) * ( inv_dfact % mod ) ) % mod ; int answer = ( ( nfact % mod ) * ( denm % mod ) ) % mod ; return answer ; } void countSubstring ( int N , int s , int k ) { int allWays = binExp ( 26 , N ) ; int noWays = 0 ; for ( int i = 0 ; i < s ; ++ i ) { int nCi = calculate_nCi ( N , i ) ; int remaining = binExp ( 25 , N - i ) ; int multiply = ( ( nCi % mod ) * ( remaining % mod ) ) % mod ; noWays = ( ( noWays % mod ) + ( multiply % mod ) ) % mod ; } int answer = ( ( allWays % mod ) - ( noWays % mod ) ) % mod ; if ( answer < 0 ) answer += mod ; cout << answer ; } int32_t main ( ) { string str = " abc " ; int k = 2 ; int s = str . length ( ) ; int N = s + k ; countSubstring ( N , s , k ) ; }