Calculate the nth Fibonacci number, mod m I was trying to output F(n) mod m to find the remainder of Fibonacci number, where F(n) could be a very big number:

# Uses python3
n, m =  [int(x) for x in input().split()]

def fib(n):
    a = [0, 1]
    if (n &lt;=1):
        return n
    else:
        for i in range(1, n):
            a.append((a[-1] + a[-2])%m)
        return a[i+1]
print (fib(n))


As I typed in 239 1000, it returns 161 as the remainder, which is correct. But with bigger inputs eg. 2816213588 239, it seems to exceed time limits, what can I do to improve the code?
Sorry, I am giving no code (I am on a phone and I don't know Python), but be aware that if m^2 is way lower than n, you could use the fact that your function gets periodical with a period maximally m^2 (as both a[-1] and a[-2] can gain m different values).

You could test in your for loop if/when you reached your period (if a[-2]==0 and a[-1]==1) and if so, variable i would indicate your period. Then you could simply grab a[n%(i-2)] as the answer, if I am not mistaken.

By the way, shouldn't the for loop range begin with 2?