給定一個(gè) n*m 的格點(diǎn)圖，包含 n 行 m 列共 n*m 個(gè)頂點(diǎn)，相鄰的頂點(diǎn)之間有一條邊。
【圖1.png】給出了一個(gè)3*4的格點(diǎn)圖的例子。

如果在圖中刪除部分頂點(diǎn)和其相鄰的邊，如上圖刪除第2行第3列和第3行第1列的頂點(diǎn)后，如【圖2.png】所示。

圖的生成樹(shù)指包含圖中的所有頂點(diǎn)和其中的一部分邊，使得任意兩個(gè)頂點(diǎn)之間都有由邊構(gòu)成的唯一路徑。如果兩個(gè)生成樹(shù)包含有不同的邊即被認(rèn)為不同，則上圖中共有31種不同的生成樹(shù)，其中a邊不選有10種，a邊選有21種。
給出格點(diǎn)圖中保留的頂點(diǎn)的信息，請(qǐng)計(jì)算該圖一共有多少種不同的生成樹(shù)。

輸入的第一行包含兩個(gè)整數(shù)n, m，用空格分隔，表示格點(diǎn)圖的行數(shù)和列數(shù)。
接下來(lái)n行，每行m個(gè)字母（中間沒(méi)有分隔字符），每個(gè)字母必然是大寫(xiě)E或大寫(xiě)N，E表示對(duì)應(yīng)的頂點(diǎn)存在，N表示對(duì)應(yīng)的頂點(diǎn)不存在。保證存在至少一個(gè)頂點(diǎn)。

輸出一行，包含一個(gè)整數(shù)，表示生成樹(shù)的個(gè)數(shù)。答案可能很大，你只需要計(jì)算答案除以1000000007的余數(shù)即可。

零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情

藍(lán)橋杯