Aqua הוא משחק חידות היגיון המשוחק על לוח מלבני המחולק ל-$r$ שורות ול-$c$ עמודות. השורות ממוספרות מ-$1$ עד $r$ מלמטה למעלה, והעמודות ממוספרות מ-$1$ עד $c$ משמאל לימין. התא בשורה ה-$i$ ובעמודה ה-$j$ מסומן ב-$(i,j)$.

הלוח מחולק למספר אזורים (כלובים) הקשירים אורתוגונלית באמצעות גבולות אנכיים ואופקיים. ליתר דיוק, כל כלוב הוא תת-קבוצה לא ריקה של תאי הלוח. כל תא בלוח שייך לכלוב אחד בדיוק. קבוצת התאים של כלוב מהווה רכיב קשירות: אם שני תאים שייכים לאותו כלוב, תמיד ניתן לעבור מתא אחד למשנהו תוך מעבר בתאים של אותו כלוב בלבד, כך שכל צעד הוא מעבר בין תאים החולקים צלע משותפת.

איור A.1: לוח עם 6 שורות, 7 עמודות ו-8 כלובים.

בכל כלוב, יוצר החידה מוזג מים מהקצוות העליונים של הכלוב. בשל כוח הכבידה, המים זורמים מטה אל התאים הנמצאים בגובה נמוך יותר. הוא מוזג מים כך שיתקיימו כל התנאים הבאים:

• כל תא הוא או מלא לחלוטין במים או ריק לחלוטין.

• כלוב יכול להיות מלא במים, ריק לחלוטין או מלא חלקית.

• בכל כלוב קיים מפלס מים מסוים $\ell$ כך שכל התאים בכלוב שמתחת למפלס זה מלאים, וכל התאים בכלוב שמעל למפלס זה ריקים. במילים אחרות, יהיו $(r_1,c_1)$ ו-$(r_2,c_2)$ שני תאים באותו כלוב כך ש-$r_1 \le r_2$; אם התא $(r_2,c_2)$ מלא, אזי גם התא $(r_1,c_1)$ חייב להיות מלא.

• הכלובים מטופלים באופן בלתי תלוי ובנפרד זה מזה. לכן, הכלל שלעיל אינו חל על תאים השייכים לכלובים שונים.

להלן דוגמה ללוח תקין:

איור A.2: לוח תקין.

להלן מספר דוגמאות ללוחות לא תקינים:

איור A.3: לוח לא תקין — התאים $(5,5)$ ו-$(5,7)$ צריכים להיות שניהם מלאים או שניהם ריקים, מכיוון שהם נמצאים באותו כלוב ובאותה שורה.

איור A.4: לוח לא תקין — התאים $(4,2)$, $(4,3)$ ו-$(4,4)$ ריקים, אך הם נמצאים באותו כלוב כמו התא $(5,2)$ המלא במים.

איור A.5: לוח לא תקין — תאים אינם יכולים להיות מלאים חלקית בלבד.

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

משימתכם היא לספור את מספר הדרכים למזוג מים לכלובים כך שכל הכללים והדרישות שלעיל יתקיימו. שתי דרכים נחשבות שונות אם ורק אם קיים תא שמלא בדרך אחת אך ריק בדרך השנייה.

קלט

השורה הראשונה של הקלט מכילה שני מספרים שלמים $r,c$ ($1 \le r,c \le 20$). $r+1$ השורות הבאות מתארות את הלוח לפי הכללים הבאים:

• כל שורה מכילה בדיוק $2\cdot c+1$ תווים, שכל אחד מהם הוא אחד מהבאים: רווח, קו תחתון (_) או קו אנכי (|).

• כל התווים במיקומי אינדקס זוגיים בשורה הראשונה ובשורה האחרונה הם קווים תחתונים, המייצגים את הגבול העליון והגבול התחתון של הלוח.

• כל קו תחתון בקלט, למעט אלו שהוזכרו לעיל, מייצג גבול כלוב אופקי בין שני תאים עוקבים באותה עמודה.

• התו הראשון והתו האחרון בכל השורות (למעט השורה הראשונה) הם קווים אנכיים, המייצגים את הגבול השמאלי והגבול הימני של הלוח.

• כל קו אנכי בקלט, למעט אלו שהוזכרו לעיל, מייצג גבול כלוב אנכי בין שני תאים עוקבים באותה שורה.

ראו את הדוגמאות להבנה טובה יותר.

לפי ההגדרה:

• אם אין גבול כלוב אופקי בין שני תאים עוקבים בעמודה, שני תאים אלו שייכים לאותו כלוב.

• אם אין גבול כלוב אנכי בין שני תאים עוקבים בשורה, שני תאים אלו שייכים לאותו כלוב.

השורה האחרונה מכילה $r$ מספרים שלמים $x_1,x_2,\ldots,x_r$ ($-1 \le x_i \le c$) המתארים את הדרישות לגבי מספר התאים המלאים בכל שורה. אם $x_i=-1$, בשורה ה-($r-i+1$) יכול להיות מספר כלשהו של תאים עם מים. אחרת, מספר התאים המלאים בשורה זו חייב להיות בדיוק $x_i$.

מובטח כי בלוח יש לכל היותר 20 כלובים.

פלט

הפלט מכיל מספר שלם אחד בדיוק — מספר הלוחות התקינים המקיימים את התנאים הנתונים, מודולו $10^9+7$.

דוגמאות

קלט 1

6 7
 _ _ _ _ _ _ _ 
| |  _ _|  _  |
| | |_ _| |_| |
| |_ _ _|  _ _|
| |  _ _| |   |
| | |_ _| |   |
|_|_ _ _|_|_ _|
6 3 7 2 2 2

פלט 1

1

הערה

הדוגמה הראשונה מתאימה לאיור A.2 שלעיל.

קלט 2

2 3
 _ _ _ 
|     |
|_ _ _|
-1 -1

פלט 2

3

קלט 3

3 3
 _ _ _ 
|  _  |
| | | |
|_|_|_|
-1 1 1

פלט 3

1