Морти покупает продукты

Давайте представим все продукты, как многочлен P, степень которого равна максимальной стоимости продукта. Коэффициентом, стоящим при i-й степени будет cnti, где cnti  — количество продуктов, стоимость которых равна i. Теперь давайте поймем, что же представляет из себя покупка. Если k = 1, то Pi — количество способов купить один товар со стоимостью i. Если k = 2, P2 = P2 то P2i — количество способов купить два товара, чтобы их суммарная стоимость была i и т.д. Нам нужно вычислить Pk. Для того, чтобы сделать это, воспользуемся бинарным возведением в степень. За кадром остается лишь вопрос о перемножении многочленов. Для того, чтобы быстро перемножать два многочлена, нужно написать быстрое преобразование Фурье с целыми числами (обратите внимание на модуль), так как очень вероятно, что быстрое преобразование Фурье, использующее вещественные числа превысит лимит времени исполнения на ограничениях в данной задаче.

После того, как многочлен Pk вычислен, остается предпосчитать префиксные суммы sumi, где sumi = sumi - 1 + Pki. Теперь ответом на запрос lr является разность sumr - suml - 1, взятая по модулю.