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