Hi, I have tried this problem a few times and keep failing due to timeout (a bit frustrating). Here's my code which runs O(n). It is based on the idea that f(n) = 2* f(n-1) - f(n-2) + f(n-m-1). Can someone give any hint what would be a better solution?

def f(n, m):
    if n < m: return 1
    if n == m: return 2

    a = [1] * (m + 1)
    a[m] = 2
    value, p = 0, 0
    for _ in range(m + 1, n + 1):
        value = 2 * a[(p+m) % (m+1)] - a[(p+m-1) % (m+1)] + a[p]
        a[p] = value
        p = (p+1) % (m+1)
    return value

Did not expect the major obstacle to be OverflowError from exponentiation of (sqrt(5)+1)/2. Horrible use of diagonalization without numpy.

EDIT: Learned the Decimal module, which helps in calculating very large decimal value. But got stuck with insufficient decimal.getcontext().prec as the value after exponentiation is very, very large (thousands? millions? or even more of digits), while I want every single digit to the left of the decimal point. I wonder if anything could be done to this intermediate step, as there is still crucial ahead before performing the final modulo opeartion. And the I obtained is also subject to significant error as it is found with np.linalg.eig(). Heck, there is even decimal.Overflow: above Emax!

EDIT 2: When I looked closely, unfortunately, this approach seems to start deviating from the results of the DP approach (which is slower but correct) for (763701899 vs 763701898). Using numpy without Decimal is even worse. When the input is 2000 3 then it is the embarrassing 973324784 vs nan vs 709134169.

EDIT 3: Stupid me to have thought about diagonalization. It's not the only option to achieve matrix exponentiation. Simple recursive divide and conquer like mergesort can do the job. And one more thing, construct your matrix according to .

Now perhaps I'm ready for Problem 109 Darts.

I am getting wrong answer for test case 11. Others are correct. There is no overflow problem, as I also checked using BigInteger, same result. Can somebody pointing ouut my mistake?