Number of ways to convert a character X to a string Y | Java 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
class GFG { final static int MOD = 1000000007 ; static long modInv ( long a ) { long p = MOD - 2 ; long s = 1 ; while ( p != 1 ) { if ( p % 2 == 1 ) s = ( s * a ) % MOD ; a = ( a * a ) % MOD ; p /= 2 ; } return ( a * s ) % MOD ; } static long findCnt ( char x , String y ) { long ans = 0 ; long fact [ ] = new long [ y . length ( ) + 1 ] ; for ( int i = 0 ; i < y . length ( ) + 1 ; i ++ ) fact [ i ] = 1 ; for ( int i = 1 ; i <= y . length ( ) ; i ++ ) fact [ i ] = ( fact [ i - 1 ] * i ) % MOD ; for ( int i = 0 ; i < y . length ( ) ; i ++ ) { if ( y . charAt ( i ) == x ) { ans += ( modInv ( fact [ i ] ) * modInv ( fact [ y . length ( ) - i - 1 ] ) ) % MOD ; ans %= MOD ; } } ans *= fact [ ( y . length ( ) - 1 ) ] ; ans %= MOD ; return ans ; } public static void main ( String [ ] args ) { char x = ' a ' ; String y = " xxayy " ; System . out . println ( findCnt ( x , y ) ) ; } }