For \(i \geq 2\), let \(a_i\) be the answer when \(N=i\). Here, the number of ways to generate a level-\(i\) gem from \(x\) level-\(1\) gems and a “level-\(k_1\) gem,” a “level-\(k_2\) gem,” \(\ldots\), and a “level-\(k_{i-x}\) gem” can be represented by \(_A C _x \prod_{j=1}^{i-x} a_{k_j}\) (where \(2 \leq k_1 \lt \ldots \lt k_{i-x} \leq i-1\).) Since the value \(a_i\) is the sum of this value over all ways to choose gems, it coincides with the coefficient of \(x^i\) in \(f(x) \prod_{j=2}^{i-1} (1+a_j x)\), where \(f(x) = _A C _0 + _A C _1 x + \ldots + _AC_A x^A\). As we only have to consider the terms of degrees at most \(n\), naively computing the polynomials (by finding \(a_i\) in order while multiplying by \((1+a_i x)\)) is an \(\mathrm {O}(N^2)\)-solution.

What is used here is polynomials of size \(\mathrm{O}(N)\) and \(\mathrm{O}(N)\) multiplications of \((1+a_i x)\), which is hard to optimize. On the other hand, a multiplication of polynomials of sizes \( \mathrm {O}(N)\) can be achieved in an \(\mathrm{O}(N \log N)\) time with FFT (Fast Fourier Transform). Therefore, we can find \(\prod (1+a_ix)\) for some given \(a_1\ldots a_N\) by the following divide-and-conquer trick in a total of \(\mathrm{O}(N (\log N)^2)\) time:

// Returns (1+a_l x)(1+a_{l+1} x)...(1+a_{r-1} x)
vector<mint> dc(int l,int r){

	if(r-l==1)return {1,a[l]};

	int m = (l+r)/2;
	return convolution(dc(l,m),dc(m,r));

}

In this problem is different in that \(a_i\) is determined dynamic and we also have to consider the product with \(f(x)\), but we can still try the following divide-and-conquer. Nevertheless, we multiply an \(\mathrm{O}(N)\)-sized polynomial \(g\) with others in the \(8\)-th and \(9\)-th lines, which causes a TLE (Time Limit Exceeded):

// Argument g represents f(x)(1+a_2 x)...(1+a_{l-1} x)
// Returns (1+a_l x)(1+a_{l+1} x)...(1+a_{r-1} x)
vector<mint> dc(int l,int r,vector<mint> g){
	
	if(r-l==1)return {1,g[l]};
	
	int m = (l+r)/2;
	vector<mint> temp = dc(l,m,g);
	return convolution(temp,dc(m,r,convolution(g,temp)));
	
}

Here, in a function call for \([l,r)\), only the terms of \(g\) of degrees \([l,r)\) are used. Thus, we can pass only this part to find the product, so that the problem is solved in a total of \(\mathrm{O}(N (\log N)^2)\) time, just as in the last example.