[contravariant]

With a better chosen dp approach you can even solve it in O(log(n)). Though at that point the extra cost of multiplying large integers becomes non-negligible.

[maxmaio]

I'm having trouble coming up with this approach on my own. could you share it please?