Number of ways to convert a character X to a string Y | C ++ implementation of the approach ; Function to find the modular - inverse ; While power > 1 ; Updating s and a ; Updating power ; Return the final answer ; Function to return the count of ways ; To store the final answer ; To store pre - computed factorials ; Computing factorials ; Loop to find the occurrences of x and update the ans ; Multiplying the answer by ( n - 1 ) ! ; Return the final answer ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MOD = 1000000007 ; long long modInv ( long long a , long long p = MOD - 2 ) { long long s = 1 ; while ( p != 1 ) { if ( p % 2 ) s = ( s * a ) % MOD ; a = ( a * a ) % MOD ; p /= 2 ; } return ( a * s ) % MOD ; } long long findCnt ( char x , string y ) { long long ans = 0 ; long long fact [ y . size ( ) + 1 ] = { 1 } ; for ( long long i = 1 ; i <= y . size ( ) ; i ++ ) fact [ i ] = ( fact [ i - 1 ] * i ) % MOD ; for ( long long i = 0 ; i < y . size ( ) ; i ++ ) { if ( y [ i ] == x ) { ans += ( modInv ( fact [ i ] ) * modInv ( fact [ y . size ( ) - i - 1 ] ) ) % MOD ; ans %= MOD ; } } ans *= fact [ ( y . size ( ) - 1 ) ] ; ans %= MOD ; return ans ; } int main ( ) { char x = ' a ' ; string y = " xxayy " ; cout << findCnt ( x , y ) ; return 0 ; }