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.