Farmer John 有一塊呈 $N$ 乘 $N$ 網格形狀的小田地（$1 \le N \le 2000$）。對於所有 $1 \le i,j \le N$，從上往下數第 $i$ 列中，從左往右數第 $j$ 個方格記為 $(i,j)$。他想在田地裡種植甜玉米和苜蓿。為此，他需要安裝一些特殊的灑水器。

位於方格 $(I,J)$ 的甜玉米灑水器會灑水到其左下方的所有方格，也就是滿足 $I \le i$ 且 $j \le J$ 的方格 $(i,j)$。

位於方格 $(I,J)$ 的苜蓿灑水器會灑水到其右上方的所有方格，也就是滿足 $i \le I$ 且 $J \le j$ 的方格 $(i,j)$。

被一個或多個甜玉米灑水器灑水的方格可以種植甜玉米；被一個或多個苜蓿灑水器灑水的方格可以種植苜蓿。但是，同時被兩種類型的灑水器灑水（或兩種類型都沒有灑水）的方格無法種植任何作物。

請幫助 FJ 求出在田地中安裝灑水器的方案數，並對 $10^9 + 7$ 取模。每個方格至多安裝一個灑水器，且每個方格都必須適合種植（也就是恰好被一種類型的灑水器灑水）。

有些方格已經被長毛牛佔據；這不妨礙這些方格適合種植，但不能在這些方格中安裝灑水器。

輸入格式

第一行包含一個整數 $N.$

對於每個 $1\le i\le N,$，第 $i+1$ 行包含一個長度為 $N$ 的字串，表示網格的第 $i$ 列。字串中的每個字元為 'W'（表示被長毛牛佔據的方格）或 '.'（未被佔據）。

輸出格式

輸出安裝灑水器的方案數除以 $10^9+7.$ 的餘數。

範例

輸入格式 1

2
..
..

輸出格式 1

28

說明

以下是方格 $(1,1)$ 可以種植甜玉米時的全部十四種可能。

CC  .C  CA  CC  .C  CA  CA  C.  CA  C.  CC  .C  CC  .C  
CC, CC, CC, .C, .C, .C, CA, CA, .A, .A, C., C., .., ..

輸入格式 2

4
..W.
..WW
WW..
...W

輸出格式 2

2304

說明

這符合下文所述第一個子任務的限制。

子任務

• 測試資料 3-4 滿足 $N\le 10$，且至多有十個未被佔據的方格。
• 測試資料 5-9 滿足 $N\le 200$。
• 測試資料 10-16 沒有額外限制。

題目作者：Benjamin Qi