สองขั้นตอนต่อไปนี้ที่กระทำบนอาร์เรย์ $x$ ซึ่งประกอบด้วยจำนวนเต็มบวก จะเรียกว่าการดำเนินการหนึ่งครั้ง:

1. เลือกสมาชิกสองตัวใดๆ ที่อยู่ติดกันใน $x$ ลดค่าของตัวหนึ่งลง $1$ และกำหนดค่าของอีกตัวหนึ่งให้เป็น $0$
2. ลบเลขศูนย์ทั้งหมดออกจาก $x$

เราจะเรียก $x$ ว่าลึกลับ (mystic) ก็ต่อเมื่อมันสามารถถูกแปลงให้เป็นลำดับว่างได้หลังจากใช้การดำเนินการจำนวนจำกัดครั้ง (อาจเป็นศูนย์ครั้ง)

กำหนดอาร์เรย์ $a$ ซึ่งประกอบด้วยจำนวนเต็ม $n$ ตัว รวมถึงจำนวนเต็ม $m$ สมาชิกแต่ละตัวของ $a$ จะเป็นจำนวนเต็มตั้งแต่ $1$ ถึง $m$ หรือไม่ก็เป็น $-1$ หน้าที่ของคุณคือแทนที่ทุกตำแหน่งที่เป็น $-1$ ใน $a$ ด้วยจำนวนเต็มใดๆ ตั้งแต่ $1$ ถึง $m$

จงหาจำนวนอาร์เรย์ลึกลับ $a$ ที่แตกต่างกันที่สามารถได้รับหลังจากการแทนที่ เนื่องจากคำตอบอาจมีค่าใหญ่มาก ให้แสดงผลลัพธ์มอดุโล $10^9 + 7$

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็มสองตัวคือ $n$ และ $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^8$)

บรรทัดที่สองของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $n$ ตัวคือ $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$ หรือ $a_i = -1$)

ข้อมูลส่งออก

แสดงจำนวนเต็มเพียงตัวเดียว ซึ่งแทนจำนวนลำดับลึกลับ $a$ ที่แตกต่างกันที่สามารถได้รับ มอดุโล $10^9 + 7$

ตัวอย่าง

ข้อมูลนำเข้าตัวอย่างที่ 1

2 2
-1 -1

ข้อมูลส่งออกตัวอย่างที่ 1

3

ข้อมูลนำเข้าตัวอย่างที่ 2

6 10
-1 -1 -1 -1 1 7

ข้อมูลส่งออกตัวอย่างที่ 2

9125

หมายเหตุ

ในชุดทดสอบแรก อาร์เรย์ $a$ คือ $[-1, -1]$ เมื่อแทนที่ $-1$ ทั้งสองตัวแล้ว ผลลัพธ์หนึ่งที่เป็นไปได้คือ $[1, 2]$ ในกรณีนี้ เราเลือกตัวเลขสองตัวที่อยู่ติดกัน: ลดตัวแรกลง $1$ และกำหนดให้ตัวที่สองเป็น $0$ จะได้ $[0, 0]$ หลังจากลบเลขศูนย์ทั้งหมดออกแล้ว ลำดับจะกลายเป็นลำดับว่าง ดังนั้น $[1, 2]$ จึงเป็นลำดับลึกลับ

ในทำนองเดียวกัน หากเราแทนที่ $-1$ ด้วย $[1, 1]$ หรือ $[2, 1]$ ลำดับทั้งสองก็สามารถถูกลดรูปให้เป็นลำดับว่างได้เช่นกัน ดังนั้น จำนวนลำดับลึกลับที่แตกต่างกันทั้งหมดจึงเท่ากับ $3$