Во времена Великого Ангуса, когда в королевстве «Бургер Кинг» ещё только складывались древние рецепты, каждый элемент массива считался отдельным ингредиентом для священного бургера. Число $$$a_i$$$ означало, какой именно ингредиент лежит на $$$i$$$-й полке королевской кладовой, всего полок было $$$n$$$.

Но в день Великого Ангусения жрецам было поручено необычное дело. Из отрезка кладовой с $$$l$$$-й по $$$r$$$-ю полку нужно было собрать ровно $$$k$$$ корзин ингредиентов, причём:

• ингредиент с $$$i$$$-й полки должен оказаться не более чем в одной корзине;
• в каждой корзине $$$\operatorname{MEX}$$$ набора ингредиентов должен быть равен $$$x$$$.

Здесь $$$\operatorname{MEX}$$$ — это наименьшее неотрицательное число, которого нет в выбранной корзине: именно оно считалось номером недостающего ингредиента в великом рецепте Ангуса.

Жрецы «Бургер Кинга» верили: если на отрезке кладовой посчитать количество способов собрать таким образом корзины, то в этот день Ангус будет особенно сочным, а королевство — сытым и довольным.

Так и поступают мудрецы: для каждого запроса с границами отрезка $$$[l, r]$$$ и числом $$$x$$$ они считают, сколькими способами можно выбрать множество из $$$k$$$ попарно непересекающихся подпоследовательностей $$$a_l, a_{l+1}, \ldots, a_r$$$ так, чтобы каждая подпоследовательность имела $$$\operatorname{MEX}$$$ равный $$$x$$$.

Обратите внимание, что две подпоследовательности считаются различными, если они состоят из элементов с различными индексами в массиве $$$a$$$. Например, в массиве $$$a = [0, 0, 0]$$$ на отрезке $$$[1,3]$$$ существует $$$7$$$ непустых подпоследовательностей с $$$\operatorname{MEX}$$$ равным $$$1$$$.

Вам предстоит выступить в роли мудреца и посчитать количество таких способов. Так как их может быть очень много, достаточно вывести ответы по модулю $$$10^9 + 7$$$.

Тесты к этой задаче состоят из восьми групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, что прохождение тестов из условия не требуется для некоторых групп. Итоговый балл за каждую группу равняется максимальному баллу, полученному за эту группу тестов по всем отправленным посылкам.