<\/p>\n
\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = 109;\r\n\r\nstruct Int{\r\n int val;\r\n\r\n operator int() const{return val;}\r\n\r\n Int(int val = 0):val(val){\r\n val %= MOD; if (val < 0) val += MOD;\r\n }\r\n inline Int& operator +=(const Int& rhs){\r\n INC(val, rhs);\r\n return *this;\r\n }\r\n inline Int operator +(const Int& rhs) const{\r\n return sum(val, rhs.val);\r\n }\r\n inline Int operator -(const Int& rhs) const{\r\n return dff(val, rhs);\r\n }\r\n};\r\n\r\nInt F[2][2][N][N], S[2][2][N][N]; bool A[N][N];\r\nint n, m;\r\n\r\nInt SS(int b1, int b2, int x1, int x2, int y1, int y2){\r\n return S[b1][b2][x2+1][y2+1] - S[b1][b2][x2+1][y1] - S[b1][b2][x1][y2+1] + S[b1][b2][x1][y1];\r\n}\r\n\r\nclass AmoebaDivOne {\r\npublic:\r\n\tint count(vector <string> T) {\r\n\r\n\t n = SZ(T), m = SZ(T[0]); REP_2(i, j, n, m){\r\n\t int t = isdigit(T[i][j]) ? T[i][j] - '0' : T[i][j] - 'a' + 10;\r\n A[2*i][2*j] = t & 1, A[2*i][2*j+1] = t & 2;\r\n A[2*i+1][2*j] = t & 4, A[2*i+1][2*j+1] = t & 8;\r\n\t }\r\n\r\n\t n <<= 1, m <<= 1; RST(F); Int res; REP(i, n){\r\n\r\n RST(S); REP_4(b1, b2, l, r, 2, 2, m, m) S[b1][b2][l+1][r+1] = S[b1][b2][l][r+1] + S[b1][b2][l+1][r] - S[b1][b2][l][r] + F[b1][b2][l][r];\r\n\r\n RST(F); REP(l, m) FOR(r, l, m){\r\n\r\n if (A[i][r]) break;\r\n\r\n F[0][0][l][r] = SS(0, 0, l, r, l, r) + Int(1);\r\n F[0][1][l][r] = SS(0, 0, l, r, r+1, m-1) + SS(0, 1, l, r, r, m-1);\r\n F[1][0][l][r] = SS(0, 0, 0, l-1, l, r) + SS(1, 0, 0, l, l, r);\r\n F[1][1][l][r] = SS(0, 0, 0, l-1, r+1, m-1) + SS(0, 1, 0, l-1, r, m-1) + SS(1, 0, 0, l, r+1, m-1) + SS(1, 1, 0, l, r, m-1);\r\n\r\n REP_2(b1, b2, 2, 2) res += F[b1][b2][l][r];\r\n }\r\n\t\t}\r\n\r\n\t\treturn res;\r\n\t}\r\n};\r\n<\/pre>\n