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)$ に水をまきます。

1 個以上のスイートコーン用スプリンクラーから水をまかれたマスでは、スイートコーンを育てられます。1 個以上のアルファルファ用スプリンクラーから水をまかれたマスでは、アルファルファを育てられます。しかし、両方の種類のスプリンクラーから水をまかれたマス（またはどちらの種類からも水をまかれないマス）では、何も育てられません。

FJ が、各マスに高々 1 個のスプリンクラーを設置し、すべてのマスを作物を育てられる状態（すなわち、ちょうど 1 種類のスプリンクラーから水をまかれる状態）にする方法の数を、$10^9 + 7$ を法として求めるのを手伝ってください。

いくつかのマスはすでに毛むくじゃらの牛に占有されています。これはそのマスで作物を育てる妨げにはなりませんが、そのようなマスにはスプリンクラーを設置できません。

入力

最初の行には整数 $N.$ が 1 つ与えられます。

各 $1\le i\le N,$ について、$i+1$ 行目にはマス目の $i$ 行目を表す長さ $N$ の文字列が与えられます。文字列の各文字は、毛むくじゃらの牛に占有されたマスを表す 'W'、または占有されていないマスを表す '.' のいずれかです。

出力

スプリンクラーを設置する方法の数を $10^9+7.$ で割った余りを出力してください。

入出力例

入力 1

2
..
..

出力 1

28

注記

以下は、$(1,1)$ でスイートコーンを育てられる場合の全 14 通りです。

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$ を満たし、占有されていないマスは高々 10 個です。
• テストケース 5–9 は $N\le 200$ を満たします。
• テストケース 10–16 には追加の制約はありません。

問題作成者：Benjamin Qi