Power function to calculate a raised to m1 under modulo 10000007
def power ( a , m1 ) : NEW_LINE INDENT if ( m1 == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT elif ( m1 == 1 ) : NEW_LINE INDENT return a NEW_LINE DEDENT elif ( m1 == 2 ) : NEW_LINE INDENT return ( a * a ) % mod NEW_LINE DEDENT elif ( m1 & 1 ) : NEW_LINE INDENT return ( a * power ( power ( a , m1 // 2 ) , 2 ) ) % mod NEW_LINE DEDENT else : NEW_LINE INDENT return power ( power ( a , m1 // 2 ) , 2 ) % mod NEW_LINE DEDENT DEDENT