令 $A(x) = \sum_{i=1}^n \frac{x^{l_i}-x^{r_i+1}}{1-x}$，则答案就是

$$ [x^s t^4] \prod_{i\ge 1} (1+tx^i)^{[x^i] A(x)} $$

经过简单的 ln-exp 推导，可以得到

$$ [x^s t^4] \exp\left(\sum_{k\ge 1} \frac{(-1)^{k-1} t^k A(x^k)}k\right) $$

展开得

$$ [x^s] \frac1{24} \left(A^4-6A(x^2)A^2+3A^2(x^2)+8A(x^3)A-6A(x^4)\right) $$

除了第一项以外，显然都可以 $O(n^3)$。第一项可以在折半后通过 Vandermonde 恒等式和双指针计算，时间复杂度 $O(n^2 \log n)$。