I just did a problem that asks you for $$$q$$$ queries of $$$[x^k](\prod_{i=1}^{n}(1+x^i))^2\ mod \ 10^9 + 7$$$. $$$n$$$ is given beforehand and $$$k$$$ is given in the queries. Constraints: $$$n,k,q \leq 10^5$$$. Is there a simple solution that doesn't involve a huge polynomials template that runs in $$$o(NK)$$$? (The time limit is 3 seconds).