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.