1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using ii = pair<int, int>;
constexpr int MX = 155, MOD = 1e9+7;
inline void add(int & x, int y) { x += y; if (x > MOD) x -= MOD; }
string S[MX];
struct fenwick_tree_2d {
int FT[MX][MX];
fenwick_tree_2d() { memset(FT, 0, sizeof FT); }
inline void update(int x, int y, int v) {
for (int i = x+1; i < MX; i += i&-i)
for (int j = y+1; j < MX; j += j&-j) add(FT[i][j], v);
}
inline int query(int x, int y) {
int ret = 0;
for (int i = x+1; i > 0; i -= i&-i)
for (int j = y+1; j > 0; j -= j&-j) add(ret, FT[i][j]);
return ret;
}
inline int query(int xl, int xr, int yl, int yr) {
int ret = query(xr, yr);
add(ret, MOD-query(xl-1, yr));
add(ret, MOD-query(xr, yl-1));
add(ret, query(xl-1, yl-1));
return ret;
}
} DP[MX][4];
int main() {
if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
int N; cin >> N;
for (int i = 0; i < N; ++i) cin >> S[i];
int ans = 0;
for (int i = 0; i < N; ++i) {
for (int a = 0; a < N; ++a) {
for (int b = a; b < N; ++b) {
if (S[i][b] != 'G') break;
int sum = 1;
int d0bb = DP[i][0].query(b,b);
int d0a1b = DP[i][0].query(a-1,b);
int d0ba1 = DP[i][0].query(b,a-1);
int d0a1a1 = DP[i][0].query(a-1,a-1);
// DP[i][0] query(b,b)-query(a-1,b)-query(b,a-1)+query(a-1,a-1);
// add(sum, DP[i][0].query(a, b, a, b));
add(sum, d0bb), add(sum, MOD-d0a1b), add(sum, MOD-d0ba1), add(sum, d0a1a1);
DP[i+1][0].update(a, b, sum);
add(ans, sum);
int d1bn1 = DP[i][1].query(b, N-1);
int d1a1n1 = DP[i][1].query(a-1, N-1);
int d1bb1 = DP[i][1].query(b,b-1);
int d1a1b1 = DP[i][1].query(a-1,b-1);
int d0bn1 = DP[i][0].query(b,N-1);
int d0a1n1 = DP[i][0].query(a-1,N-1);
// DP[i][1] query(b, N-1)-query(a-1,N-1)-query(b,b-1)+query(a-1, b-1)
// DP[i][0] query(b, N-1)-query(a-1, N-1)-query(b,b)+query(a-1, b)
// sum = DP[i][1].query(a, b, b, N-1);
sum = 0; add(sum, d1bn1), add(sum, MOD-d1a1n1), add(sum, MOD-d1bb1), add(sum, d1a1b1);
// add(sum, DP[i][0].query(a, b, b+1, N-1));
add(sum, d0bn1), add(sum, MOD-d0a1n1), add(sum, MOD-d0bb), add(sum, d0a1b);
DP[i+1][1].update(a, b, sum);
add(ans, sum);
int d2ab = DP[i][2].query(a, b);
//int d21b = 0; //DP[i][2].query(-1, b);
int d2aa1 = DP[i][2].query(a, a-1);
//int d21a1 = 0; //DP[i][2].query(-1, a-1);
//int d01b = 0; //DP[i][0].query(-1, b);
//int d01a1 = 0; //DP[i][0].query(-1, a-1);
// DP[i][2] query(a,b)-query(-1,b)-query(a, a-1)+query(-1, a-1)
// DP[i][0] query(a-1, b)-query(-1,b)-query(a-1,a-1)+query(-1,a-1)
// sum = DP[i][2].query(0, a, a, b);
sum = 0; add(sum, d2ab); //add(sum, MOD-d21b),
add(sum, MOD-d2aa1);//, add(sum, d21a1);
// add(sum, DP[i][0].query(0, a-1, a, b));
add(sum, d0a1b);//, add(sum, MOD-d01b),
add(sum, MOD-d0a1a1);//, add(sum, d01a1);
DP[i+1][2].update(a, b, sum);
add(ans, sum);
// int d01n1 = 0;//DP[i][0].query(-1,N-1);
// int d11n1 = 0;//DP[i][1].query(-1, N-1);
// int d11b1 = 0;//DP[i][1].query(-1, b-1);
int d2an1 = DP[i][2].query(a, N-1);
// int d21n1 = 0;//DP[i][2].query(-1, N-1);
// DP[i][3] query(a, N-1)-query(-1,N-1)-query(a,b-1)+query(-1, b-1)
// DP[i][0] query(a-1, N-1)-query(-1,N-1)-query(a-1,b)+query(-1, b)
// DP[i][1] query(a-1, N-1)-query(-1,N-1)-query(a-1,b-1)+query(-1, b-1)
// DP[i][2] query(a, N-1)-query(-1,N-1)-query(a,b)+query(-1, b)
sum = DP[i][3].query(a, N-1); add(sum, MOD-DP[i][3].query(a,b-1));
// add(sum, DP[i][0].query(0, a-1, b+1, N-1));
add(sum, d0a1n1);//, add(sum, MOD-d01n1),
add(sum, MOD-d0a1b);//, add(sum, d01b);
// add(sum, DP[i][1].query(0, a-1, b, N-1));
add(sum, d1a1n1);//, add(sum, MOD-d11n1),
add(sum, MOD-d1a1b1);//, add(sum, d11b1);
// add(sum, DP[i][2].query(0, a, b+1, N-1));
add(sum, d2an1);
//add(sum, MOD-d21n1),
add(sum, MOD-d2ab);//, add(sum, d21b);
DP[i+1][3].update(a, b, sum);
add(ans, sum);
}
}
}
cout << ans%MOD;
}
|
