لعبة 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