#include using namespace std; #define rep(i,a,b) for(int i=a;i= mod ? x - mod : x; } template int add(int x, T... y) { return add(x, add(y...)); } int sub(int x, int y) { return add(x, mod - y); } int mul(int x, int y) { return 1LL * x * y % mod; } template int mul(int x, T... y) { return mul(x, mul(y...)); } int modpow(int a, long long b) { int ret = 1; while (b > 0) { if (b & 1) ret = 1LL * ret * a % mod; a = 1LL * a * a % mod; b >>= 1; } return ret; } int modinv(int a) { return modpow(a, mod - 2); } //----------------------------------------------------------------------------------- int H, W; string _S[501]; int Q, A[501], B[501], C[501], D[501]; //----------------------------------------------------------------------------------- string S[501]; int c[501][501], w[501][501], cw[501][501], cww[501][501]; void pre(int HH, int WW) { rep(y, 1, HH + 1) rep(x, 0, WW + 1) c[y][x] = w[y][x] = cw[y][x] = cww[y][x] = 0; rep(y, 1, HH + 1) { rep(x, 1, WW + 1) { if (S[y][x] == 'c') { c[y][x] = add(c[y][x - 1], 1); w[y][x] = w[y][x - 1]; cw[y][x] = cw[y][x - 1]; cww[y][x] = cww[y][x - 1]; } else { c[y][x] = c[y][x - 1]; w[y][x] = add(w[y][x - 1], 1); cw[y][x] = add(cw[y][x - 1], c[y][x - 1]); cww[y][x] = add(cww[y][x - 1], cw[y][x - 1]); } } } } int get(int y, int L, int R) { int res = sub(cww[y][R], cww[y][L - 1]); int cnt_w = sub(w[y][R], w[y][L - 1]); res = sub(res, mul(c[y][L - 1], cnt_w, sub(cnt_w, 1), modinv(2))); res = sub(res, mul(cw[y][L - 1], cnt_w)); return res; } //----------------------------------------------------------------------------------- int ans[101010]; int main() { cin >> H >> W; rep(y, 1, H + 1) cin >> _S[y], _S[y] = "#" + _S[y]; cin >> Q; rep(q, 0, Q) scanf("%d%d%d%d", &A[q], &B[q], &C[q], &D[q]); rep(y, 1, max(H, W) + 1) rep(x, 0, max(H, W) + 1) S[y] += "#"; rep(y, 1, H + 1) rep(x, 1, W + 1) S[y][x] = _S[y][x]; pre(H, W); rep(q, 0, Q) rep(y, A[q], C[q] + 1) ans[q] = add(ans[q], get(y, B[q], D[q])); //rep(y, 1, H + 1) cout << S[y] << endl; //rep(q, 0, Q) printf("%d\n", ans[q]); rep(y, 1, H + 1) rep(x, 1, W + 1) S[y][W - x + 1] = _S[y][x]; pre(H, W); rep(q, 0, Q) rep(y, A[q], C[q] + 1) ans[q] = add(ans[q], get(y, W - D[q] + 1, W - B[q] + 1)); //rep(y, 1, H + 1) cout << S[y] << endl; //rep(q, 0, Q) printf("%d\n", ans[q]); rep(y, 1, H + 1) rep(x, 1, W + 1) S[x][y] = _S[y][x]; pre(W, H); rep(q, 0, Q) rep(y, B[q], D[q] + 1) ans[q] = add(ans[q], get(y, A[q], C[q])); //rep(y, 1, H + 1) cout << S[y] << endl; //rep(q, 0, Q) printf("%d\n", ans[q]); rep(y, 1, H + 1) rep(x, 1, W + 1) S[x][H - y + 1] = _S[y][x]; pre(W, H); rep(q, 0, Q) rep(y, B[q], D[q] + 1) ans[q] = add(ans[q], get(y, H - C[q] + 1, H - A[q] + 1)); //rep(y, 1, H + 1) cout << S[y] << endl; rep(q, 0, Q) printf("%d\n", ans[q]); }