def fib_rec ( a, b, p, q, num ):
    if ( num == 0 ):
        return b
    if ( num % 2 == 0 ):
        return fib_rec(a, b, p*p+q*q, 2*p*q+q*q, num/2)
    return fib_rec(b*q+a*q+a*p, b*p+a*q, p, q, num-1)

def power_fib ( N,M ):
    # write your code here
    numo = N**M
    return fib_rec(1, 0, 0, 1, numo)%10000103

power_fib ( 3,2 )