Вы играете в небольшую игру под названием «Удаление камней».

В ряд расположены $n$ кучек камней. В кучке $i$ находится $a_i$ камней. Ваша задача — удалить все камни с помощью следующих операций:

• Операция 1: выбрать одну кучку и удалить из неё не менее 2 камней.
• Операция 2: выбрать непрерывный отрезок номеров $[l,r]$, где $1\le l\le r\le n$ и $r-l\ge 2$, и удалить ровно по 1 камню из каждой кучки на этом отрезке.

Вы можете выполнять эти две операции в любом порядке любое количество раз, пока ни одну операцию больше нельзя будет выполнить. Если в итоге удастся удалить все камни, вы победите.

Возможно, вы уже начали считать что-нибудь вроде «количества существенно различных способов выполнения операций», но на практике обнаружили, что всё время проигрываете. Поэтому вы решили немного схитрить: в начале игры у вас в руке тайно спрятано $k$ камней. До выполнения всех операций вы можете и обязаны добавить эти камни в одну или несколько кучек. Вы надеетесь, что это повысит шансы на победу, но понимаете, что из-за этого можно проиграть даже в игре, которую изначально можно было выиграть.

Теперь вы можете свободно выбрать начальную позицию: каждое $a_i$ может быть любым целым числом из диапазона $[l_i,r_i]$. Требуется найти количество начальных позиций, для которых существует хотя бы один способ победить. Поскольку ответ велик, выведите его по модулю $(10^9+7)$. Две начальные позиции различны тогда и только тогда, когда существует хотя бы один индекс $1\le i\le n$, для которого значения $a_i$ различаются. Обратите внимание: под «начальной позицией» понимается позиция до добавления $k$ камней.

Входные данные

Данные считываются из файла stone.in.

В этой задаче несколько наборов тестовых данных. Первая строка содержит положительное целое число $T$ — количество наборов. Затем последовательно следуют наборы данных.

Для каждого набора первая строка содержит два целых числа $n,k$ — количество кучек и количество добавляемых камней соответственно. Следующие $n$ строк содержат по два неотрицательных целых числа $l_i,r_i$, задающих диапазон начального количества камней в каждой кучке.

Выходные данные

Результат выводится в файл stone.out.

Для каждого набора выведите в отдельной строке одно целое число — количество позиций, в которых можно победить, по модулю $(10^9+7)$.

Примеры

Входные данные 1

1
4 1
0 1
0 1
0 1
0 1

Выходные данные 1

14

Примечание

Всего существует $2^4=16$ возможных начальных позиций. Можно доказать, что для всех позиций, кроме $(0,0,0,0)$ и $(1,0,0,1)$, существует способ победить. Например, для начальной позиции $(1,0,1,0)$ можно добавить находящийся в руке 1 камень во вторую кучку, получив позицию $(1,1,1,0)$, а затем один раз выполнить операцию 2 на отрезке $[1,3]$.

Пример 2

См. файлы stone/stone2.in и stone/stone2.ans в каталоге участника.

Пример 3

См. файлы stone/stone3.in и stone/stone3.ans в каталоге участника.

Пример 4

См. файлы stone/stone4.in и stone/stone4.ans в каталоге участника.

Ограничения

Для 100% данных гарантируется $T\le 10$, $3\le n\le 1000$, $0\le l_i\le r_i\le 10^9$, $0\le k\le 100$.