I went down some time consuming dead ends on this problem. I focused on combinations and binomial coefficients. But these suffered from number variable overflow. What I initially missed was that the results of each n follows a fibonacci sequence. It is easy once you realise that.

