أنت تلعب لعبة صغيرة تسمى «إزالة الحصى».

هناك $n$ كومة من الحصى مصطفة في صف، وتحتوي الكومة رقم $i$ على $a_i$ حصاة. مهمتك هي إزالة جميع الحصى باستخدام العمليتين التاليتين:

• العملية الأولى: اختر كومة واحدة، وأزل منها حصاتين على الأقل.
• العملية الثانية: اختر مجالًا متصلًا من أرقام الكومات $[l,r]$، حيث $1\leq l\leq r\leq n$ و$r-l\geq 2$، وأزل حصاة واحدة بالضبط من كل كومة في هذا المجال.

يمكنك تنفيذ هاتين العمليتين بأي ترتيب وأي عدد من المرات، حتى يتعذر تنفيذ أي عملية أخرى. وتفوز إذا تمكنت في النهاية من إزالة جميع الحصى.

ربما بدأت بالفعل في حساب أمور مثل «كم عدد طرق تنفيذ العمليات المختلفة جوهريًا؟»، لكنك تجد أثناء اللعب أنك تخسر دائمًا. لذلك تقرر اللجوء إلى حيلة صغيرة: عند بدء اللعبة، تخفي $k$ حصاة في يدك، وقبل تنفيذ أي عملية، يمكنك ويجب عليك وضع هذه الحصى في كومة واحدة أو عدة كومات. وتأمل أن يزيد ذلك من فرص فوزك، لكنك تدرك أيضًا أنه قد يجعلك تخسر لعبة كان من الممكن الفوز بها أصلًا.

يمكنك الآن اختيار وضع ابتدائي بحرية للعب، وتحديدًا، يمكن اختيار كل $a_i$ ليكون أي عدد صحيح في المجال $[l_i,r_i]$. تريد حساب عدد الأوضاع الابتدائية التي توجد فيها طريقة واحدة على الأقل للفوز. ولأن الإجابة كبيرة، فلا يلزمك إلا إخراج باقي قسمتها على $(10^9+7)$. يختلف وضعان ابتدائيان إذا وفقط إذا وجد $i$ واحد على الأقل يحقق $1\leq i\leq 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\ 0)$، ثم تنفيذ العملية الثانية مرة واحدة على المجال $[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\leq 10$، و$3\leq n\leq 1000$، و$0\leq l_i\leq r_i\leq 10^9$، و$0\leq k\leq 100$.