Sum of all N | Python 3 program for the above approach ; Function to find a ^ b efficiently ; Base Case ; To store the value of a ^ b ; Multiply temp by a until b is not 0 ; Return the final ans a ^ b ; Function to find sum of all N - digit palindromic number divisible by 9 ; Base Case ; If N is even , decrease ways by 1 ; Find the total number of ways ; Iterate over [ 1 , N ] and find the sum at each index ; Print the final Sum ; Driver Code
MOD = 1000000007 NEW_LINE def power ( a , b ) : NEW_LINE INDENT if ( b == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT temp = power ( a , b // 2 ) NEW_LINE temp = ( temp * temp ) % MOD NEW_LINE if ( b % 2 != 0 ) : NEW_LINE INDENT temp = ( temp * a ) % MOD NEW_LINE DEDENT return temp NEW_LINE DEDENT def palindromicSum ( N ) : NEW_LINE INDENT sum = 0 NEW_LINE if ( N == 1 ) : NEW_LINE INDENT print ( "9" ) NEW_LINE return NEW_LINE DEDENT if ( N == 2 ) : NEW_LINE INDENT print ( "99" ) NEW_LINE return NEW_LINE DEDENT ways = N // 2 NEW_LINE if ( N % 2 == 0 ) : NEW_LINE INDENT ways -= 1 NEW_LINE DEDENT res = power ( 9 , ways - 1 ) NEW_LINE for i in range ( N ) : NEW_LINE INDENT sum = sum * 10 + 45 * res NEW_LINE sum %= MOD NEW_LINE DEDENT print ( sum ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 3 NEW_LINE palindromicSum ( N ) NEW_LINE DEDENT