تُسمى الخطوتان التاليتان، على مصفوفة $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$.