Count ways to make the number formed by K concatenations of a numeric string divisible by 5 | Python program for the above approach ; Function to find the value of a ^ b modulo 1000000007 ; Stores the resultant value a ^ b ; Find the value of a ^ b ; Function to count the number of ways such that the formed number is divisible by 5 by removing digits ; Stores the count of ways ; Find the count for string S ; If the digit is 5 or 0 ; Find the count of string for K concatenation of string S ; Find the total count ; Driver Code
MOD = 1000000007 NEW_LINE def exp_mod ( a , b ) : NEW_LINE INDENT ret = 1 NEW_LINE while ( b ) : NEW_LINE INDENT if ( b & 1 ) : NEW_LINE INDENT ret = ret * a % MOD NEW_LINE DEDENT b >>= 1 NEW_LINE a = a * a % MOD NEW_LINE DEDENT return ret NEW_LINE DEDENT def countOfWays ( s , k ) : NEW_LINE INDENT N = len ( s ) NEW_LINE ans = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT if ( s [ i ] == '5' or s [ i ] == '0' ) : NEW_LINE INDENT ans = ( ans + exp_mod ( 2 , i ) ) % MOD NEW_LINE DEDENT DEDENT q = exp_mod ( 2 , N ) NEW_LINE qk = exp_mod ( q , k ) NEW_LINE inv = exp_mod ( q - 1 , MOD - 2 ) NEW_LINE ans = ans * ( qk - 1 ) % MOD NEW_LINE ans = ans * inv % MOD NEW_LINE return ans NEW_LINE DEDENT S = "1256" NEW_LINE K = 1 NEW_LINE print ( countOfWays ( S , K ) ) NEW_LINE