Number of ways to convert a character X to a string Y | Python3 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
MOD = 1000000007 ; NEW_LINE def modInv ( a , p = MOD - 2 ) : NEW_LINE INDENT s = 1 ; NEW_LINE while ( p != 1 ) : NEW_LINE INDENT if ( p % 2 ) : NEW_LINE INDENT s = ( s * a ) % MOD ; NEW_LINE DEDENT a = ( a * a ) % MOD ; NEW_LINE p //= 2 ; NEW_LINE DEDENT return ( a * s ) % MOD ; NEW_LINE DEDENT def findCnt ( x , y ) : NEW_LINE INDENT ans = 0 ; NEW_LINE fact = [ 1 ] * ( len ( y ) + 1 ) ; NEW_LINE for i in range ( 1 , len ( y ) ) : NEW_LINE INDENT fact [ i ] = ( fact [ i - 1 ] * i ) % MOD ; NEW_LINE DEDENT for i in range ( len ( y ) ) : NEW_LINE INDENT if ( y [ i ] == x ) : NEW_LINE INDENT ans += ( modInv ( fact [ i ] ) * modInv ( fact [ len ( y ) - i - 1 ] ) ) % MOD ; NEW_LINE ans %= MOD ; NEW_LINE DEDENT DEDENT ans *= fact [ ( len ( y ) - 1 ) ] ; NEW_LINE ans %= MOD ; NEW_LINE return ans ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT x = ' a ' ; NEW_LINE y = " xxayy " ; NEW_LINE print ( findCnt ( x , y ) ) ; NEW_LINE DEDENT