Count of N digit Numbers having no pair of equal consecutive Digits | Iterative Function to calculate ( x ^ y ) % mod in O ( log y ) ; Initialize result ; Update x if x >= mod ; If x is divisible by mod ; If y is odd , multiply x with result ; y must be even now y = y / 2 ; Function to count the number of N - digit numbers with no equal pair of consecutive digits ; Base Case ; Driver Code
def power ( x , y , mod ) : NEW_LINE INDENT res = 1 ; NEW_LINE x = x % mod ; NEW_LINE if ( x == 0 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT while ( y > 0 ) : NEW_LINE INDENT if ( ( y & 1 ) == 1 ) : NEW_LINE INDENT res = ( res * x ) % mod ; NEW_LINE DEDENT y = y >> 1 ; NEW_LINE x = ( x * x ) % mod ; NEW_LINE DEDENT return res ; NEW_LINE DEDENT def count ( N ) : NEW_LINE INDENT if ( N == 1 ) : NEW_LINE INDENT print ( 10 ) ; NEW_LINE return ; NEW_LINE DEDENT print ( power ( 9 , N , 1000000007 ) ) ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 3 ; NEW_LINE count ( N ) ; NEW_LINE DEDENT