שני הצעדים הבאים, על מערך $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$.