# How to compute the first n coefficients using number theoretic transform (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(n\log n)$$ or $$O(q\log q)$$? I think this is to be done using NTT but cannot get an exact method. I tried Divide and Conquer but it is $$O(qn\log n)$$.