Kamu sedang memainkan sebuah permainan kecil bernama “Mengambil Batu”.

Terdapat $n$ tumpukan batu yang berjajar, dengan tumpukan ke-$i$ berisi $a_i$ batu. Tugasmu adalah mengambil semua batu melalui operasi berikut:

• Operasi pertama: pilih sebuah tumpukan dan ambil sedikitnya $2$ batu dari tumpukan tersebut;
• Operasi kedua: pilih interval nomor berurutan $[l,r]$ ($1 \le l \le r \le n$) yang memenuhi $r-l \ge 2$, lalu ambil tepat $1$ batu dari setiap tumpukan di dalamnya.

Kamu boleh melakukan kedua operasi tersebut sebanyak apa pun dan dalam urutan apa pun, sampai tidak ada operasi yang dapat dilakukan lagi. Kamu menang jika pada akhirnya semua batu berhasil diambil.

Mungkin kamu sudah mulai menghitung hal-hal seperti “berapa banyak cara operasi yang pada dasarnya berbeda”, tetapi ketika benar-benar bermain, kamu justru menyadari bahwa kamu selalu kalah. Karena itu, kamu berencana melakukan sedikit kecurangan: pada awal permainan, kamu diam-diam menyembunyikan $k$ batu di tangan. Sebelum melakukan operasi apa pun, kamu boleh dan wajib menaruh batu-batu tersebut ke dalam satu atau beberapa tumpukan. Kamu berharap ini meningkatkan peluang menang, tetapi kamu juga tahu bahwa hal ini mungkin membuatmu kalah dalam permainan yang sebelumnya dapat dimenangkan.

Sekarang, kamu dapat bebas memilih keadaan awal permainan. Secara khusus, setiap $a_i$ dapat dipilih sebagai bilangan bulat mana pun dalam rentang $[l_i,r_i]$. Kamu ingin menghitung banyaknya keadaan awal yang memiliki setidaknya satu cara untuk menang. Karena jawabannya sangat besar, kamu hanya perlu mengeluarkannya modulo $(10^9+7)$. Dua keadaan awal berbeda jika dan hanya jika terdapat setidaknya satu $1 \le i \le n$ sehingga nilai $a_i$ pada keduanya berbeda. Perhatikan bahwa “keadaan awal” di sini berarti keadaan sebelum kamu menambahkan $k$ batu.

Masukan

Baca data dari berkas stone.in.

Soal ini memiliki beberapa kasus uji. Baris pertama berisi sebuah bilangan bulat positif $T$ yang menyatakan banyaknya kasus uji. Berikutnya, setiap kasus uji diberikan secara berurutan.

Untuk setiap kasus uji, baris pertama berisi dua bilangan bulat $n,k$, yang masing-masing menyatakan banyaknya tumpukan batu dan banyaknya batu yang ditambahkan. Berikutnya terdapat $n$ baris, masing-masing berisi dua bilangan bulat nonnegatif $l_i,r_i$ yang menyatakan rentang banyaknya batu awal pada setiap tumpukan.

Keluaran

Tulis keluaran ke berkas stone.out.

Untuk setiap kasus uji, keluarkan satu baris berisi sebuah bilangan bulat yang menyatakan banyaknya keadaan yang dapat dimenangkan, modulo $(10^9+7)$.

Contoh

Masukan 1

1
4 1
0 1
0 1
0 1
0 1

Keluaran 1

14

Penjelasan

Terdapat $2^4=16$ keadaan awal yang mungkin. Dapat dibuktikan bahwa selain dua keadaan awal $(0\ 0\ 0\ 0)$ dan $(1\ 0\ 0\ 1)$ yang tidak dapat dimenangkan, semua keadaan awal lainnya memiliki cara untuk menang. Misalnya, jika keadaan awalnya $(1\ 0\ 1\ 0)$, kamu dapat menaruh $1$ batu di tanganmu ke tumpukan kedua sehingga keadaannya menjadi $(1\ 1\ 1\ 0)$, lalu melakukan operasi kedua sekali pada interval $[1,3]$.

Contoh 2

Lihat stone/stone2.in dan stone/stone2.ans di direktori peserta.

Contoh 3

Lihat stone/stone3.in dan stone/stone3.ans di direktori peserta.

Contoh 4

Lihat stone/stone4.in dan stone/stone4.ans di direktori peserta.

Batasan

Untuk $100\%$ data, dijamin bahwa $T \le 10$, $3 \le n \le 1000$, $0 \le l_i \le r_i \le 10^9$, dan $0 \le k \le 100$.