คุณกำลังเล่นเกมเล็ก ๆ ชื่อ “นำก้อนหินออก”

มีกองหิน $n$ กองเรียงเป็นแถว กองที่ $i$ มีหิน $a_i$ ก้อน งานของคุณคือนำหินทั้งหมดออกด้วยการดำเนินการต่อไปนี้:

• การดำเนินการที่หนึ่ง: เลือกกองหินหนึ่งกอง แล้วนำหินออกจากกองนั้นอย่างน้อย 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 ก้อนในมือลงในกองที่ $2$ ให้สถานะกลายเป็น $(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 \le 10$, $3 \le n \le 1000$, $0 \le l_i \le r_i \le 10^9$, $0 \le k \le 100$