this platform testing the provided cases only, for more efficient you shouldn't use built-in functions.

😭

so use the reduce is optimial because O(n) ?

Gorgeous! But not optimal performance.

Oh my, you're entirely correct. It was the eager calculation of all the options which slowed down my executions. This was very instructive. Pardon me.

I just tried it and it worked.

This is non-applicable. The tests no longer allow this as a solution. They required me to do extensive caching and still ran in over six seconds. Several others have reported the steep performance requirements which did not allow such solutions.

Very well organized ideas. Readable, simple, maintainable. Splendid use of Python's features. The formatting is neat but not best practice.

O(n) runtime with a single pass, no extra copies or list resizing. ++points

This is a very interesting kata. There are trivial answers, and then there are very difficult (and more efficient) answers which could utilize advanced number theory and/or combinatorics. It's amazing just how difficult counting problems can actually be.