Tarazlanmış alt çoxluqlar#11242

Tarazlanmış alt çoxluqlar

2 saniyə

128 meqabayt

Çox çətin

Peyin Johnun otlağı, hər bir $i (1 \leq i \leq n), j (1 \leq j \leq n)$ i~(1 \le i \le n), j~(1 \le j \le n) üçün $(i, j)$ cütləri ilə işarələnmiş böyük bir 2D şəbəkə kimi təsəvvür edilə bilər. Bu hüceyrələrin bəzilərində ot var.

Şəbəkə hüceyrələrinin boş olmayan alt çoxluğu "tarazlaşdırılmış" adlanır, əgər aşağıdakı şərtlər yerinə yetirilirsə:

- Alt çoxluqdakı bütün hüceyrələr ot ehtiva edir. - Alt çoxluq **4**-ə qoşulmuşdur. Bu, alt çoxluqdakı istənilən hüceyrədən digərinə bir yolun olması deməkdir və yolun ardıcıl iki hüceyrəsi üfüqi və ya şaquli qonşudur. - Əgər ('x[1]', **y**) və ('x[2]', **y**) ('x[1]' ≤ 'x[2]') hüceyrələri alt çoxluğa aiddirsə, onda 'x[1]' ≤ **x** ≤ 'x[2]' olan bütün (**x**, **y**) hüceyrələri də alt çoxluğa aiddir. - Əgər (**x**, 'y[1]') və (**x**, 'y[2]') ('y[1]' ≤ 'y[2]') hüceyrələri alt çoxluğa aiddirsə, onda 'y[1]' ≤ **y** ≤ 'y[2]' olan bütün (**x**, **y**) hüceyrələri də alt çoxluğa aiddir.

Tarazlaşdırılmış alt çoxluqların sayını $1 0^{9} + 7$ 10^9 + 7 modulu ilə hesablayın.

Giriş

Birinci sətir $n (1 \leq n \leq 150)$ n~(1 \le n \le 150) ədədini ehtiva edir.

Növbəti $n$ sətirin hər biri $n$ simvoldan ibarət bir sətir ehtiva edir. Üstdən $i$ -ci sətirin $j$ -ci simvolu, əgər hüceyrə $(i, j)$ ot ehtiva edirsə, $G$ simvoluna, əks halda isə nöqtə simvoluna bərabərdir.

Çıxış

Tarazlaşdırılmış alt çoxluqların sayını $1 0^{9} + 7$ 10^9 + 7 modulu ilə çıxarın.

Nümunələr

Nümunə 1. Bu test üçün bütün $4$ -ə qoşulmuş alt çoxluqlar tarazlaşdırılmışdır.

G.  .G  ..  ..  GG  .G  ..  G.  GG  .G  G.  GG  GG
.., .., G., .G, .., .G, GG, G., G., GG, GG, .G, GG

Nümunə 2. Aşağıda, ikinci şərti ( $4$ -ə qoşulma) təmin edən, lakin üçüncü şərti təmin etməyən bir alt çoxluq nümunəsi verilmişdir:

GG..
.G..
GG..
....

Nümunə 1

Nümunə 2