Ви граєте в невелику гру під назвою «Вилучення камінців».

Є $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

Пояснення до прикладу 1

Є $2^4=16$ можливих початкових позицій. Можна довести, що лише з позицій $(0\ 0\ 0\ 0)$ та $(1\ 0\ 0\ 1)$ перемогти неможливо; для решти існує спосіб перемогти. Наприклад, для початкової позиції $(1\ 0\ 1\ 0)$ можна покласти камінець із руки в другу купку, отримавши позицію $(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$.