Orositlər 2: Yoncanın Qayıdışı
Fermer Cohnun n x n ölçüsündə bir torpaq sahəsi var. Bu sahə, yuxarıdan i-ci sıranın solundakı j-ci kvadrat (i, j) ilə göstərilir, burada 1 ≤ i, j ≤ n. Cohn sahəsində şirin qarğıdalı və yonca yetişdirmək istəyir və bunun üçün xüsusi suvarma cihazları quraşdırmalıdır.
Şirin qarğıdalı çiləyicisi (I, J) kvadratında yerləşdirildikdə, sol alt küncdəki bütün kvadratları sulayır: yəni (i, j) üçün I ≤ i və j ≤ J.
Yonca çiləyicisi (I, J) kvadratında yerləşdirildikdə, sağ üst küncdəki bütün kvadratları sulayır: yəni (i, j) üçün i ≤ I və J ≤ j.
Bir və ya bir neçə şirin qarğıdalı çiləyicisi ilə sulanan kvadratda şirin qarğıdalı yetişdirilə bilər; bir və ya bir neçə yonca çiləyicisi ilə sulanan kvadratda yonca yetişdirilə bilər. Lakin hər iki tip çiləyici ilə (və ya heç biri ilə) sulanan kvadratda heç nə yetişməz.
Cohnə hər kvadratın məhsuldar olması üçün (yəni yalnız bir tip çiləyici ilə sulanması) çiləyiciləri sahəyə necə yerləşdirə biləcəyini (modul 10^9 + 7) müəyyən etməyə kömək edin.
Bəzi kvadratlar artıq yunlu inəklərlə doludur; bu, həmin sahələrin məhsuldar olmasına mane olmur, lakin bu kvadratlara çiləyicilər quraşdırıla bilməz.
Giriş Məlumatları
Birinci sətir n (1 ≤ n ≤ 2000) tək tam ədədini ehtiva edir. Hər bir i üçün (1 ≤ i ≤ n) i + 1-ci sətir n uzunluğunda bir sətir ehtiva edir və şəbəkənin i-ci sıranı göstərir. Sətirin hər bir simvolu ya 'W' (yunlu inəklə dolu kvadrat) ya da '.' (boş kvadrat) ilə təmsil olunur.
Çıxış Məlumatları
Çiləyicilərin yerləşdirilmə üsullarının sayının 10^9 + 7 ilə bölünməsindən qalanı çıxarın.
Nümunə
Budur, şirin qarğıdalının (1, 1) kvadratında yetişə biləcəyi on dörd imkan.
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., .., ..