Its the same as naive coin change

Simple DP knapsack will work ig.

At first let's solve easier problem with $$$3$$$ coins . Suppose that $$$a_0,a_1,a_2$$$ denotes coins and $$$d_0,d_1,d_2$$$ number of times we can use each coin respectively and $$$v$$$ value we need to get for some query .

Now let's suppose that $$$d_i=inf$$$ for each $$$i$$$ , this is trivial dynamic programming problem (we could do precalculation and then then answer queries) .

If we know answer for above trivial problem we will use inclusion-exclusion dp to answer real problem , suppose that we don't want to count "bad" (one that exceeds $$$d_i$$$) for $$$i=0$$$ . Then we should substract from answer every such possible way that : number of times i used $$$(a_0)$$$ exceeds $$$d_0$$$ . This could be done with taking every number $$$x$$$ , where $$$x>d_0$$$ and substring number of ways to get $$$v-x*a_0$$$ with $$$a_1,a_2$$$ from answer . We will solve similiarly for $$$(a_1),(a_2)$$$ , then for $$$(a_0,a_1)$$$ , $$$(a_1,a_2)$$$ ... and so on .

But we can't iterate over all possible $$$x$$$-es because we would get TLE . Instead of that we will iterate over all possible sums we can get with $$$a_1,a_2$$$ let's denote it as $$$j$$$ . We notice that every $$$x*a_0$$$ is just a form of $$$v-j-(d_0+1)*a_0$$$ and thus we can substract number of ways to get $$$v-j-(d_0+1)*a_0$$$ * number of ways to get $$$j$$$ (with $$$a_1,a_2$$$) instead of iterating over $$$x$$$ . This is solved in $$$O(N*q*max(v))$$$ .