# How to solve this using NTT?

I need to find the first N coefficients of $$\prod_{i = 1}^{i = Q}(1 + x^{a_i})^{b_i}$$ modulo a NTT favourable prime. Can someone suggest an algorithm with worst-case complexity $$O(nlogn)$$ or $$O(qlogq)$$? I think this is to be done using NTT but cannot get of an exact method.I tried Divide and Conquer but it is $$O(qnlogn)$$.