Ah, Project Euler #109: Darts! This intriguing problem delves into the surprisingly vast possibilities of checkout throws in the classic game. With the unique "doubles out" rule adding a strategic twist, the number of potential three-dart combinations quickly skyrockets. Cracking this challenge requires clever deduction and efficient search algorithms, rewarding the solver with a deep appreciation for the dartboard's arithmetic elegance. How to play darts Prepare for a satisfying brain-teaser that blends logic and probability into a fun, mathematical adventure!

"There are exactly 14 distinct ways to checkout on a score of 6"... There seems to be more. For example:

s1 s1 s1 s1 d1
s1 s1 s2 d1 
s2 s1 s1 d1
s1 s2 s1 d1
s1 s1 d1 d1
d1 s1 s1 d1
s1 d1 s1 d1

These are not included in the list. Which rules crossed them out?

The infinite number of darts are not very friendly. I suppose dynamic programming is not applicable for larger input. My DP approach got TLE #7, #8 and MemoryError from #9 onwards. If you're interested, here is part of my code snippet:

mod = int(1e9) + 9
darts = [1] + [0] * N
for n in xrange(N+1):
    for m in xrange(1, 61):
        if n + m > N:
            break
        darts[n+m] += darts[n] * one_dart[m]
        darts[n+m] %= mod

EDIT: Learn about linear recurrence relation matrix (of size ), and then think about constructing the matrix (of size ) that can be feeded to a cumulative vector. Start with the vector [1] + [0] * 60. Perform matrix exponentiation (divide and conquer, very straightforward) that is . And finally, pick the double ending elements from the final vector of . Problem 114 has a relevant approach.

Can please someone suggest an idea for less than O(N) solution to deal with test cases 9 and above.

I assume that there should be analytic formula for coefficients of series expansion of generating function just can't find one.

what is modulo 10^9+9 how to represent answer in that format