I am solving this problem on SPOJ Upper Right King (Hard):There is a king in the lower left corner of the \$ n \times n \$ chess board. The king can move one step right, one step up or one step up-right. How many ways are there for him to reach the upper right corner of the board? Give the answer modulo 1000003.The numbers to be output are the central Delannoy numbers.I've written a solution in Python with a time complexity of \$ O(n(\log m)^2) \$.  But it's showing time limit exceeded.  Can anyone help me out with this?import mathMAX = 10000002MOD = 1000003# Extended euclidean algorithm for modular inversedef egcd(a, b):    if a == 0:        return (b, 0, 1)    else:        g, y, x = egcd(b % a, a)        return (g, x - (b // a) * y, y)def modinv(a, m):    g, x, y = egcd(a, m)    if g != 1:        return 0    else:        return x % mt = raw_input()t = long(t)fact = []for i in range(0,MAX):    fact.append(0)fact[0]=1fact[1]=1for i in range(2,MAX):    fact[i] = (i%MOD * fact[i-1]%MOD)%MODwhile t:    n = raw_input()    n = long(n)    n = n-1    Sum = 1    prod = ((n+1)%MOD * (n)%MOD)%MOD    increment = n+1    decrement = n    Sum = (Sum%MOD + prod%MOD)%MOD    for k in range(0,n-1):        temp_prod = (prod%MOD * (increment+1)%MOD * (decrement-1)%MOD)%MOD        prod = temp_prod        fct = fact[k+2]        fat2 = (fct%MOD * fct%MOD)%MOD     #   print fat2,modinv(fat2,MOD)        result = (temp_prod%MOD * modinv(fat2,MOD))%MOD        Sum = (Sum%MOD + result%MOD)%MOD        increment = increment + 1        decrement = decrement - 1    print %ld %(Sum)    t = t-1How can I reduce the complexity of this problem in order to have it accepted?
Central Delannoy numbers
python;mathematics;combinatorics;time limit exceeded;chess