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