אתם משחקים במשחק קטן בשם ״הסרת אבנים״.

יש $n$ ערמות אבנים המסודרות בשורה, ובערמה ה־$i$ יש $a_i$ אבנים. משימתכם להסיר את כל האבנים באמצעות הפעולות הבאות:

• פעולה ראשונה: בחרו ערמה והסירו ממנה לפחות $2$ אבנים;
• פעולה שנייה: בחרו קטע רציף של מספרי ערמות $[l,r]$, כאשר $1\leq l\leq r\leq n$ ו־$r-l\geq2$, והסירו בדיוק אבן אחת מכל ערמה בקטע.

אפשר לבצע כל אחת משתי הפעולות בכל סדר וכמה פעמים שתרצו, עד שאי אפשר לבצע עוד פעולה. אם בסוף הסרתם את כל האבנים, ניצחתם.

אולי כבר התחלתם לחשב דברים כמו ״כמה דרכי פעולה שונות מהותית קיימות״, אבל כשאתם משחקים בפועל אתם מגלים שאתם תמיד מפסידים. לכן החלטתם להשתמש בתכסיס קטן: בתחילת המשחק אתם מחביאים בידכם $k$ אבנים. לפני ביצוע הפעולות, אתם רשאים וחייבים להוסיף את האבנים האלה לערמה אחת או לכמה ערמות. אתם מקווים שזה ישפר את סיכוייכם לנצח, אבל יודעים שזה גם עלול לגרום לכם להפסיד משחק שבו הייתם יכולים לנצח.

כעת אתם יכולים לבחור בחופשיות את המצב ההתחלתי. ליתר דיוק, כל $a_i$ יכול להיות כל מספר שלם בטווח $[l_i,r_i]$. חשבו בכמה מצבים התחלתיים קיימת לפחות דרך אחת לנצח. מכיוון שהתשובה גדולה, יש להדפיס אותה מודולו $(10^9+7)$ בלבד. שני מצבים התחלתיים שונים אם ורק אם קיים לפחות $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\leq10$, $3\leq n\leq1000$, $0\leq l_i\leq r_i\leq10^9$, $0\leq k\leq100$.