Count ways to make the number formed by K concatenations of a numeric string divisible by 5 | Java 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
class GFG { static long MOD = 1000000007 ; public static long exp_mod ( long a , long b ) { long ret = 1 ; for ( ; b > 0 ; b >>= 1 , a = a * a % MOD ) { if ( ( b & 1 ) > 0 ) ret = ret * a % MOD ; } return ret ; } public static long countOfWays ( String s , int k ) { int N = s . length ( ) ; long ans = 0 ; for ( int i = 0 ; i < N ; i ++ ) { if ( s . charAt ( i ) == '5' || s . charAt ( 0 ) == '0' ) { ans = ( ans + exp_mod ( 2 , i ) ) % MOD ; } } long q = exp_mod ( 2 , N ) ; long qk = exp_mod ( q , k ) ; long inv = exp_mod ( q - 1 , MOD - 2 ) ; ans = ans * ( qk - 1 ) % MOD ; ans = ans * inv % MOD ; return ans ; } public static void main ( String args [ ] ) { String S = "1256" ; int K = 1 ; System . out . println ( countOfWays ( S , K ) ) ; } }