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)$ .