結果
問題 | No.2708 Jewel holder |
ユーザー | drken1215 |
提出日時 | 2024-03-31 14:08:15 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 33,984 bytes |
コンパイル時間 | 2,406 ms |
コンパイル使用メモリ | 219,516 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-30 19:01:31 |
合計ジャッジ時間 | 3,163 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,820 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,816 KB |
testcase_03 | AC | 2 ms
6,816 KB |
testcase_04 | AC | 2 ms
6,816 KB |
testcase_05 | AC | 2 ms
6,816 KB |
testcase_06 | AC | 1 ms
6,820 KB |
testcase_07 | AC | 2 ms
6,820 KB |
testcase_08 | AC | 2 ms
6,816 KB |
testcase_09 | AC | 2 ms
6,820 KB |
testcase_10 | AC | 2 ms
6,820 KB |
testcase_11 | AC | 2 ms
6,820 KB |
testcase_12 | AC | 2 ms
6,816 KB |
testcase_13 | AC | 2 ms
6,820 KB |
testcase_14 | AC | 2 ms
6,816 KB |
testcase_15 | AC | 2 ms
6,816 KB |
testcase_16 | AC | 2 ms
6,820 KB |
testcase_17 | AC | 2 ms
6,816 KB |
testcase_18 | AC | 2 ms
6,820 KB |
testcase_19 | AC | 2 ms
6,820 KB |
ソースコード
#include <bits/stdc++.h>using namespace std;using pint = pair<int, int>;using pll = pair<long long, long long>;template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }// 4-neighbor (or 8-neighbor)const vector<int> dx = {1, 0, -1, 0, 1, -1, 1, -1};const vector<int> dy = {0, 1, 0, -1, 1, 1, -1, -1};/*///////////////////////////////////////////////////////*/// debug/*///////////////////////////////////////////////////////*/#define DEBUG 1#define COUT(x) if (DEBUG) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endltemplate<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P){ return s << '<' << P.first << ", " << P.second << '>'; }template<class T> ostream& operator << (ostream &s, vector<T> P){ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }template<class T> ostream& operator << (ostream &s, deque<T> P){ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }template<class T> ostream& operator << (ostream &s, vector<vector<T> > P){ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }template<class T> ostream& operator << (ostream &s, set<T> P){ for (auto it : P) { s << "<" << it << "> "; } return s; }template<class T> ostream& operator << (ostream &s, multiset<T> P){ for (auto it : P) { s << "<" << it << "> "; } return s; }template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P){ for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }/*///////////////////////////////////////////////////////*/// QCFium 法/*///////////////////////////////////////////////////////*/#pragma GCC target("avx2")#pragma GCC optimize("Ofast")#pragma GCC optimize("unroll-loops")/*/////////////////////////////*/// modint, FPS/*/////////////////////////////*/// modinttemplate<int MOD> struct Fp {// inner valuelong long val;// constructorconstexpr Fp() : val(0) { }constexpr Fp(long long v) : val(v % MOD) {if (val < 0) val += MOD;}constexpr long long get() const { return val; }constexpr int get_mod() const { return MOD; }// arithmetic operatorsconstexpr Fp operator + () const { return Fp(*this); }constexpr Fp operator - () const { return Fp(0) - Fp(*this); }constexpr Fp operator + (const Fp &r) const { return Fp(*this) += r; }constexpr Fp operator - (const Fp &r) const { return Fp(*this) -= r; }constexpr Fp operator * (const Fp &r) const { return Fp(*this) *= r; }constexpr Fp operator / (const Fp &r) const { return Fp(*this) /= r; }constexpr Fp& operator += (const Fp &r) {val += r.val;if (val >= MOD) val -= MOD;return *this;}constexpr Fp& operator -= (const Fp &r) {val -= r.val;if (val < 0) val += MOD;return *this;}constexpr Fp& operator *= (const Fp &r) {val = val * r.val % MOD;return *this;}constexpr Fp& operator /= (const Fp &r) {long long a = r.val, b = MOD, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}val = val * u % MOD;if (val < 0) val += MOD;return *this;}constexpr Fp pow(long long n) const {Fp res(1), mul(*this);while (n > 0) {if (n & 1) res *= mul;mul *= mul;n >>= 1;}return res;}constexpr Fp inv() const {Fp res(1), div(*this);return res / div;}// other operatorsconstexpr bool operator == (const Fp &r) const {return this->val == r.val;}constexpr bool operator != (const Fp &r) const {return this->val != r.val;}constexpr Fp& operator ++ () {++val;if (val >= MOD) val -= MOD;return *this;}constexpr Fp& operator -- () {if (val == 0) val += MOD;--val;return *this;}constexpr Fp operator ++ (int) const {Fp res = *this;++*this;return res;}constexpr Fp operator -- (int) const {Fp res = *this;--*this;return res;}friend constexpr istream& operator >> (istream &is, Fp<MOD> &x) {is >> x.val;x.val %= MOD;if (x.val < 0) x.val += MOD;return is;}friend constexpr ostream& operator << (ostream &os, const Fp<MOD> &x) {return os << x.val;}friend constexpr Fp<MOD> pow(const Fp<MOD> &r, long long n) {return r.pow(n);}friend constexpr Fp<MOD> inv(const Fp<MOD> &r) {return r.inv();}};// Binomial coefficienttemplate<class mint> struct BiCoef {vector<mint> fact_, inv_, finv_;constexpr BiCoef() {}constexpr BiCoef(int n) : fact_(n, 1), inv_(n, 1), finv_(n, 1) {init(n);}constexpr void init(int n) {fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);int MOD = fact_[0].get_mod();for(int i = 2; i < n; i++){fact_[i] = fact_[i-1] * i;inv_[i] = -inv_[MOD%i] * (MOD/i);finv_[i] = finv_[i-1] * inv_[i];}}constexpr mint com(int n, int k) const {if (n < k || n < 0 || k < 0) return 0;return fact_[n] * finv_[k] * finv_[n-k];}constexpr mint fact(int n) const {if (n < 0) return 0;return fact_[n];}constexpr mint inv(int n) const {if (n < 0) return 0;return inv_[n];}constexpr mint finv(int n) const {if (n < 0) return 0;return finv_[n];}};namespace NTT {long long modpow(long long a, long long n, int mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}long long modinv(long long a, int mod) {long long b = mod, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}u %= mod;if (u < 0) u += mod;return u;}int calc_primitive_root(int mod) {if (mod == 2) return 1;if (mod == 167772161) return 3;if (mod == 469762049) return 3;if (mod == 754974721) return 11;if (mod == 998244353) return 3;int divs[20] = {};divs[0] = 2;int cnt = 1;long long x = (mod - 1) / 2;while (x % 2 == 0) x /= 2;for (long long i = 3; i * i <= x; i += 2) {if (x % i == 0) {divs[cnt++] = i;while (x % i == 0) x /= i;}}if (x > 1) divs[cnt++] = x;for (int g = 2;; g++) {bool ok = true;for (int i = 0; i < cnt; i++) {if (modpow(g, (mod - 1) / divs[i], mod) == 1) {ok = false;break;}}if (ok) return g;}}int get_fft_size(int N, int M) {int size_a = 1, size_b = 1;while (size_a < N) size_a <<= 1;while (size_b < M) size_b <<= 1;return max(size_a, size_b) << 1;}// number-theoretic transformtemplate<class mint> void trans(vector<mint> &v, bool inv = false) {if (v.empty()) return;int N = (int)v.size();int MOD = v[0].get_mod();int PR = calc_primitive_root(MOD);static bool first = true;static vector<long long> vbw(30), vibw(30);if (first) {first = false;for (int k = 0; k < 30; ++k) {vbw[k] = modpow(PR, (MOD - 1) >> (k + 1), MOD);vibw[k] = modinv(vbw[k], MOD);}}for (int i = 0, j = 1; j < N - 1; j++) {for (int k = N >> 1; k > (i ^= k); k >>= 1);if (i > j) swap(v[i], v[j]);}for (int k = 0, t = 2; t <= N; ++k, t <<= 1) {long long bw = vbw[k];if (inv) bw = vibw[k];for (int i = 0; i < N; i += t) {mint w = 1;for (int j = 0; j < t/2; ++j) {int j1 = i + j, j2 = i + j + t/2;mint c1 = v[j1], c2 = v[j2] * w;v[j1] = c1 + c2;v[j2] = c1 - c2;w *= bw;}}}if (inv) {long long invN = modinv(N, MOD);for (int i = 0; i < N; ++i) v[i] = v[i] * invN;}}// for garnerstatic constexpr int MOD0 = 754974721;static constexpr int MOD1 = 167772161;static constexpr int MOD2 = 469762049;using mint0 = Fp<MOD0>;using mint1 = Fp<MOD1>;using mint2 = Fp<MOD2>;static const mint1 imod0 = 95869806; // modinv(MOD0, MOD1);static const mint2 imod1 = 104391568; // modinv(MOD1, MOD2);static const mint2 imod01 = 187290749; // imod1 / MOD0;// small case (T = mint, long long)template<class T> vector<T> naive_mul(const vector<T> &A, const vector<T> &B) {if (A.empty() || B.empty()) return {};int N = (int)A.size(), M = (int)B.size();vector<T> res(N + M - 1);for (int i = 0; i < N; ++i)for (int j = 0; j < M; ++j)res[i + j] += A[i] * B[j];return res;}// mul by convolutiontemplate<class mint> vector<mint> mul(const vector<mint> &A, const vector<mint> &B) {if (A.empty() || B.empty()) return {};int N = (int)A.size(), M = (int)B.size();if (min(N, M) < 30) return naive_mul(A, B);int MOD = A[0].get_mod();int size_fft = get_fft_size(N, M);if (MOD == 998244353) {vector<mint> a(size_fft), b(size_fft), c(size_fft);for (int i = 0; i < N; ++i) a[i] = A[i];for (int i = 0; i < M; ++i) b[i] = B[i];trans(a), trans(b);vector<mint> res(size_fft);for (int i = 0; i < size_fft; ++i) res[i] = a[i] * b[i];trans(res, true);res.resize(N + M - 1);return res;}vector<mint0> a0(size_fft, 0), b0(size_fft, 0), c0(size_fft, 0);vector<mint1> a1(size_fft, 0), b1(size_fft, 0), c1(size_fft, 0);vector<mint2> a2(size_fft, 0), b2(size_fft, 0), c2(size_fft, 0);for (int i = 0; i < N; ++i)a0[i] = A[i].val, a1[i] = A[i].val, a2[i] = A[i].val;for (int i = 0; i < M; ++i)b0[i] = B[i].val, b1[i] = B[i].val, b2[i] = B[i].val;trans(a0), trans(a1), trans(a2), trans(b0), trans(b1), trans(b2);for (int i = 0; i < size_fft; ++i) {c0[i] = a0[i] * b0[i];c1[i] = a1[i] * b1[i];c2[i] = a2[i] * b2[i];}trans(c0, true), trans(c1, true), trans(c2, true);mint mod0 = MOD0, mod01 = mod0 * MOD1;vector<mint> res(N + M - 1);for (int i = 0; i < N + M - 1; ++i) {int y0 = c0[i].val;int y1 = (imod0 * (c1[i] - y0)).val;int y2 = (imod01 * (c2[i] - y0) - imod1 * y1).val;res[i] = mod01 * y2 + mod0 * y1 + y0;}return res;}};// Formal Power Seriestemplate<typename mint> struct FPS : vector<mint> {using vector<mint>::vector;// constructorconstexpr FPS(const vector<mint> &r) : vector<mint>(r) {}// core operatorconstexpr FPS pre(int siz) const {return FPS(begin(*this), begin(*this) + min((int)this->size(), siz));}constexpr FPS rev() const {FPS res = *this;reverse(begin(res), end(res));return res;}constexpr FPS& normalize() {while (!this->empty() && this->back() == 0) this->pop_back();return *this;}// basic operatorconstexpr FPS operator - () const noexcept {FPS res = (*this);for (int i = 0; i < (int)res.size(); ++i) res[i] = -res[i];return res;}constexpr FPS operator + (const mint &v) const { return FPS(*this) += v; }constexpr FPS operator + (const FPS &r) const { return FPS(*this) += r; }constexpr FPS operator - (const mint &v) const { return FPS(*this) -= v; }constexpr FPS operator - (const FPS &r) const { return FPS(*this) -= r; }constexpr FPS operator * (const mint &v) const { return FPS(*this) *= v; }constexpr FPS operator * (const FPS &r) const { return FPS(*this) *= r; }constexpr FPS operator / (const mint &v) const { return FPS(*this) /= v; }constexpr FPS operator / (const FPS &r) const { return FPS(*this) /= r; }constexpr FPS operator % (const FPS &r) const { return FPS(*this) %= r; }constexpr FPS operator << (int x) const { return FPS(*this) <<= x; }constexpr FPS operator >> (int x) const { return FPS(*this) >>= x; }constexpr FPS& operator += (const mint &v) {if (this->empty()) this->resize(1);(*this)[0] += v;return *this;}constexpr FPS& operator += (const FPS &r) {if (r.size() > this->size()) this->resize(r.size());for (int i = 0; i < (int)r.size(); ++i) (*this)[i] += r[i];return this->normalize();}constexpr FPS& operator -= (const mint &v) {if (this->empty()) this->resize(1);(*this)[0] -= v;return *this;}constexpr FPS& operator -= (const FPS &r) {if (r.size() > this->size()) this->resize(r.size());for (int i = 0; i < (int)r.size(); ++i) (*this)[i] -= r[i];return this->normalize();}constexpr FPS& operator *= (const mint &v) {for (int i = 0; i < (int)this->size(); ++i) (*this)[i] *= v;return *this;}constexpr FPS& operator *= (const FPS &r) {return *this = NTT::mul((*this), r);}constexpr FPS& operator /= (const mint &v) {assert(v != 0);mint iv = modinv(v);for (int i = 0; i < (int)this->size(); ++i) (*this)[i] *= iv;return *this;}// division, r must be normalized (r.back() must not be 0)constexpr FPS& operator /= (const FPS &r) {assert(!r.empty());assert(r.back() != 0);this->normalize();if (this->size() < r.size()) {this->clear();return *this;}int need = (int)this->size() - (int)r.size() + 1;*this = (rev().pre(need) * r.rev().inv(need)).pre(need).rev();return *this;}constexpr FPS& operator %= (const FPS &r) {assert(!r.empty());assert(r.back() != 0);this->normalize();FPS q = (*this) / r;return *this -= q * r;}constexpr FPS& operator <<= (int x) {FPS res(x, 0);res.insert(res.end(), begin(*this), end(*this));return *this = res;}constexpr FPS& operator >>= (int x) {FPS res;res.insert(res.end(), begin(*this) + x, end(*this));return *this = res;}constexpr mint eval(const mint &v) {mint res = 0;for (int i = (int)this->size()-1; i >= 0; --i) {res *= v;res += (*this)[i];}return res;}// advanced operation// df/dxconstexpr FPS diff() const {int n = (int)this->size();FPS res(n-1);for (int i = 1; i < n; ++i) res[i-1] = (*this)[i] * i;return res;}// \int f dxconstexpr FPS integral() const {int n = (int)this->size();FPS res(n+1, 0);for (int i = 0; i < n; ++i) res[i+1] = (*this)[i] / (i+1);return res;}// inv(f), f[0] must not be 0constexpr FPS inv(int deg) const {assert((*this)[0] != 0);if (deg < 0) deg = (int)this->size();FPS res({mint(1) / (*this)[0]});for (int i = 1; i < deg; i <<= 1) {res = (res + res - res * res * pre(i << 1)).pre(i << 1);}res.resize(deg);return res;}constexpr FPS inv() const {return inv((int)this->size());}// log(f) = \int f'/f dx, f[0] must be 1constexpr FPS log(int deg) const {assert((*this)[0] == 1);FPS res = (diff() * inv(deg)).integral();res.resize(deg);return res;}constexpr FPS log() const {return log((int)this->size());}// exp(f), f[0] must be 0constexpr FPS exp(int deg) const {assert((*this)[0] == 0);FPS res(1, 1);for (int i = 1; i < deg; i <<= 1) {res = res * (pre(i << 1) - res.log(i << 1) + 1).pre(i << 1);}res.resize(deg);return res;}constexpr FPS exp() const {return exp((int)this->size());}// pow(f) = exp(e * log f)constexpr FPS pow(long long e, int deg) const {if (e == 0) {FPS res(deg, 0);res[0] = 1;return res;}long long i = 0;while (i < (int)this->size() && (*this)[i] == 0) ++i;if (i == (int)this->size() || i > (deg - 1) / e) return FPS(deg, 0);mint k = (*this)[i];FPS res = ((((*this) >> i) / k).log(deg) * e).exp(deg) * mint(k).pow(e) << (e * i);res.resize(deg);return res;}constexpr FPS pow(long long e) const {return pow(e, (int)this->size());}// sqrt(f), f[0] must be 1constexpr FPS sqrt_base(int deg) const {assert((*this)[0] == 1);mint inv2 = mint(1) / 2;FPS res(1, 1);for (int i = 1; i < deg; i <<= 1) {res = (res + pre(i << 1) * res.inv(i << 1)).pre(i << 1);for (mint &x : res) x *= inv2;}res.resize(deg);return res;}constexpr FPS sqrt_base() const {return sqrt_base((int)this->size());}// friend operatorsfriend constexpr FPS diff(const FPS &f) { return f.diff(); }friend constexpr FPS integral(const FPS &f) { return f.integral(); }friend constexpr FPS inv(const FPS &f, int deg) { return f.inv(deg); }friend constexpr FPS inv(const FPS &f) { return f.inv((int)f.size()); }friend constexpr FPS log(const FPS &f, int deg) { return f.log(deg); }friend constexpr FPS log(const FPS &f) { return f.log((int)f.size()); }friend constexpr FPS exp(const FPS &f, int deg) { return f.exp(deg); }friend constexpr FPS exp(const FPS &f) { return f.exp((int)f.size()); }friend constexpr FPS pow(const FPS &f, long long e, int deg) { return f.pow(e, deg); }friend constexpr FPS pow(const FPS &f, long long e) { return f.pow(e, (int)f.size()); }friend constexpr FPS sqrt_base(const FPS &f, int deg) { return f.sqrt_base(deg); }friend constexpr FPS sqrt_base(const FPS &f) { return f.sqrt_base((int)f.size()); }};/*/////////////////////////////*/// Union-Find/*/////////////////////////////*/// Union-Findstruct UnionFind {// core membervector<int> par, nex;// constructorUnionFind() { }UnionFind(int N) : par(N, -1), nex(N) {init(N);}void init(int N) {par.assign(N, -1);nex.resize(N);for (int i = 0; i < N; ++i) nex[i] = i;}// core methodsint root(int x) {if (par[x] < 0) return x;else return par[x] = root(par[x]);}bool same(int x, int y) {return root(x) == root(y);}bool merge(int x, int y) {x = root(x), y = root(y);if (x == y) return false;if (par[x] > par[y]) swap(x, y); // merge techniquepar[x] += par[y];par[y] = x;swap(nex[x], nex[y]);return true;}int size(int x) {return -par[root(x)];}// get groupvector<int> group(int x) {vector<int> res({x});while (nex[res.back()] != x) res.push_back(nex[res.back()]);return res;}vector<vector<int>> groups() {vector<vector<int>> member(par.size());for (int v = 0; v < (int)par.size(); ++v) {member[root(v)].push_back(v);}vector<vector<int>> res;for (int v = 0; v < (int)par.size(); ++v) {if (!member[v].empty()) res.push_back(member[v]);}return res;}// debugfriend ostream& operator << (ostream &s, UnionFind uf) {const vector<vector<int>> &gs = uf.groups();for (const vector<int> &g : gs) {s << "group: ";for (int v : g) s << v << " ";s << endl;}return s;}};/*/////////////////////////////*/// Segment Tree/*/////////////////////////////*/// Segment Treetemplate<class Monoid> struct SegmentTree {using Func = function<Monoid(Monoid, Monoid)>;// core memberint N;Func OP;Monoid IDENTITY;// inner dataint log, offset;vector<Monoid> dat;// constructorSegmentTree() {}SegmentTree(int n, const Func &op, const Monoid &identity) {init(n, op, identity);}SegmentTree(const vector<Monoid> &v, const Func &op, const Monoid &identity) {init(v, op, identity);}void init(int n, const Func &op, const Monoid &identity) {N = n;OP = op;IDENTITY = identity;log = 0, offset = 1;while (offset < N) ++log, offset <<= 1;dat.assign(offset * 2, IDENTITY);}void init(const vector<Monoid> &v, const Func &op, const Monoid &identity) {init((int)v.size(), op, identity);build(v);}void pull(int k) {dat[k] = OP(dat[k * 2], dat[k * 2 + 1]);}void build(const vector<Monoid> &v) {assert(N == (int)v.size());for (int i = 0; i < N; ++i) dat[i + offset] = v[i];for (int k = offset - 1; k > 0; --k) pull(k);}int size() const {return N;}Monoid operator [] (int i) const {return dat[i + offset];}// update A[i], i is 0-indexed, O(log N)void set(int i, const Monoid &v) {assert(0 <= i && i < N);int k = i + offset;dat[k] = v;while (k >>= 1) pull(k);}// get [l, r), l and r are 0-indexed, O(log N)Monoid prod(int l, int r) {assert(0 <= l && l <= r && r <= N);Monoid val_left = IDENTITY, val_right = IDENTITY;l += offset, r += offset;for (; l < r; l >>= 1, r >>= 1) {if (l & 1) val_left = OP(val_left, dat[l++]);if (r & 1) val_right = OP(dat[--r], val_right);}return OP(val_left, val_right);}Monoid all_prod() {return dat[1];}// get max r that f(get(l, r)) = True (0-indexed), O(log N)// f(IDENTITY) need to be Trueint max_right(const function<bool(Monoid)> f, int l = 0) {if (l == N) return N;l += offset;Monoid sum = IDENTITY;do {while (l % 2 == 0) l >>= 1;if (!f(OP(sum, dat[l]))) {while (l < offset) {l = l * 2;if (f(OP(sum, dat[l]))) {sum = OP(sum, dat[l]);++l;}}return l - offset;}sum = OP(sum, dat[l]);++l;} while ((l & -l) != l); // stop if l = 2^ereturn N;}// get min l that f(get(l, r)) = True (0-indexed), O(log N)// f(IDENTITY) need to be Trueint min_left(const function<bool(Monoid)> f, int r = -1) {if (r == 0) return 0;if (r == -1) r = N;r += offset;Monoid sum = IDENTITY;do {--r;while (r > 1 && (r % 2)) r >>= 1;if (!f(OP(dat[r], sum))) {while (r < offset) {r = r * 2 + 1;if (f(OP(dat[r], sum))) {sum = OP(dat[r], sum);--r;}}return r + 1 - offset;}sum = OP(dat[r], sum);} while ((r & -r) != r);return 0;}// debugfriend ostream& operator << (ostream &s, const SegmentTree &seg) {for (int i = 0; i < (int)seg.size(); ++i) {s << seg[i];if (i != (int)seg.size() - 1) s << " ";}return s;}};// Lazy Segment Treetemplate<class Monoid, class Action> struct LazySegmentTree {// various function typesusing FuncMonoid = function<Monoid(Monoid, Monoid)>;using FuncAction = function<Monoid(Action, Monoid)>;using FuncComposition = function<Action(Action, Action)>;// core memberint N;FuncMonoid OP;FuncAction ACT;FuncComposition COMP;Monoid IDENTITY_MONOID;Action IDENTITY_ACTION;// inner dataint log, offset;vector<Monoid> dat;vector<Action> lazy;// constructorLazySegmentTree() {}LazySegmentTree(int n, const FuncMonoid op, const FuncAction act, const FuncComposition comp,const Monoid &identity_monoid, const Action &identity_action) {init(n, op, act, comp, identity_monoid, identity_action);}LazySegmentTree(const vector<Monoid> &v,const FuncMonoid op, const FuncAction act, const FuncComposition comp,const Monoid &identity_monoid, const Action &identity_action) {init(v, op, act, comp, identity_monoid, identity_action);}void init(int n, const FuncMonoid op, const FuncAction act, const FuncComposition comp,const Monoid &identity_monoid, const Action &identity_action) {N = n, OP = op, ACT = act, COMP = comp;IDENTITY_MONOID = identity_monoid, IDENTITY_ACTION = identity_action;log = 0, offset = 1;while (offset < N) ++log, offset <<= 1;dat.assign(offset * 2, IDENTITY_MONOID);lazy.assign(offset * 2, IDENTITY_ACTION);}void init(const vector<Monoid> &v,const FuncMonoid op, const FuncAction act, const FuncComposition comp,const Monoid &identity_monoid, const Action &identity_action) {init((int)v.size(), op, act, comp, identity_monoid, identity_action);build(v);}void build(const vector<Monoid> &v) {assert(N == (int)v.size());for (int i = 0; i < N; ++i) dat[i + offset] = v[i];for (int k = offset - 1; k > 0; --k) pull_dat(k);}int size() const {return N;}// basic functions for lazy segment treevoid pull_dat(int k) {dat[k] = OP(dat[k * 2], dat[k * 2 + 1]);}void apply_lazy(int k, const Action &f) {dat[k] = ACT(f, dat[k]);if (k < offset) lazy[k] = COMP(f, lazy[k]);}void push_lazy(int k) {apply_lazy(k * 2, lazy[k]);apply_lazy(k * 2 + 1, lazy[k]);lazy[k] = IDENTITY_ACTION;}void pull_dat_deep(int k) {for (int h = 1; h <= log; ++h) pull_dat(k >> h);}void push_lazy_deep(int k) {for (int h = log; h >= 1; --h) push_lazy(k >> h);}// setter and getter, update A[i], i is 0-indexed, O(log N)void set(int i, const Monoid &v) {assert(0 <= i && i < N);int k = i + offset;push_lazy_deep(k);dat[k] = v;pull_dat_deep(k);}Monoid get(int i) {assert(0 <= i && i < N);int k = i + offset;push_lazy_deep(k);return dat[k];}Monoid operator [] (int i) {return get(i);}// apply f for index ivoid apply(int i, const Action &f) {assert(0 <= i && i < N);int k = i + offset;push_lazy_deep(k);dat[k] = ACT(f, dat[k]);pull_dat_deep(k);}// apply f for interval [l, r)void apply(int l, int r, const Action &f) {assert(0 <= l && l <= r && r <= N);if (l == r) return;l += offset, r += offset;for (int h = log; h >= 1; --h) {if (((l >> h) << h) != l) push_lazy(l >> h);if (((r >> h) << h) != r) push_lazy((r - 1) >> h);}int original_l = l, original_r = r;for (; l < r; l >>= 1, r >>= 1) {if (l & 1) apply_lazy(l++, f);if (r & 1) apply_lazy(--r, f);}l = original_l, r = original_r;for (int h = 1; h <= log; ++h) {if (((l >> h) << h) != l) pull_dat(l >> h);if (((r >> h) << h) != r) pull_dat((r - 1) >> h);}}// get prod of interval [l, r)Monoid prod(int l, int r) {assert(0 <= l && l <= r && r <= N);if (l == r) return IDENTITY_MONOID;l += offset, r += offset;for (int h = log; h >= 1; --h) {if (((l >> h) << h) != l) push_lazy(l >> h);if (((r >> h) << h) != r) push_lazy(r >> h);}Monoid val_left = IDENTITY_MONOID, val_right = IDENTITY_MONOID;for (; l < r; l >>= 1, r >>= 1) {if (l & 1) val_left = OP(val_left, dat[l++]);if (r & 1) val_right = OP(dat[--r], val_right);}return OP(val_left, val_right);}Monoid all_prod() {return dat[1];}// get max r that f(get(l, r)) = True (0-indexed), O(log N)// f(IDENTITY) need to be Trueint max_right(const function<bool(Monoid)> f, int l = 0) {if (l == N) return N;l += offset;push_lazy_deep(l);Monoid sum = IDENTITY_MONOID;do {while (l % 2 == 0) l >>= 1;if (!f(OP(sum, dat[l]))) {while (l < offset) {push_lazy(l);l = l * 2;if (f(OP(sum, dat[l]))) {sum = OP(sum, dat[l]);++l;}}return l - offset;}sum = OP(sum, dat[l]);++l;} while ((l & -l) != l); // stop if l = 2^ereturn N;}// get min l that f(get(l, r)) = True (0-indexed), O(log N)// f(IDENTITY) need to be Trueint min_left(const function<bool(Monoid)> f, int r = -1) {if (r == 0) return 0;if (r == -1) r = N;r += offset;push_lazy_deep(r - 1);Monoid sum = IDENTITY_MONOID;do {--r;while (r > 1 && (r % 2)) r >>= 1;if (!f(OP(dat[r], sum))) {while (r < offset) {push_lazy(r);r = r * 2 + 1;if (f(OP(dat[r], sum))) {sum = OP(dat[r], sum);--r;}}return r + 1 - offset;}sum = OP(dat[r], sum);} while ((r & -r) != r);return 0;}// debug streamfriend ostream& operator << (ostream &s, LazySegmentTree seg) {for (int i = 0; i < (int)seg.size(); ++i) {s << seg[i];if (i != (int)seg.size() - 1) s << " ";}return s;}// dumpvoid dump() {for (int i = 0; i <= log; ++i) {for (int j = (1 << i); j < (1 << (i + 1)); ++j) {cout << "{" << dat[j] << "," << lazy[j] << "} ";}cout << endl;}}};/*/////////////////////////////*/// Solver/*/////////////////////////////*//*const long long INF = 1LL<<60;int main() {int N, M;cin >> N >> M;vector<long long> A(N);for (int i = 0; i < N; ++i) cin >> A[i];using Edge = pair<int, long long>;using Graph = vector<vector<Edge>>;Graph G(N);for (int i = 0; i < M; ++i) {long long a, b, c;cin >> a >> b >> c;--a, --b;G[a].emplace_back(b, c);//G[b].emplace_back(a, c);}vector<long long> dp(N, -INF);vector<bool> negative(N, false);dp[0] = A[0];for (int iter = 0; iter < N; ++iter) {for (int v = 0; v < N; ++v) {if (dp[v] <= -INF/2) continue;for (auto e : G[v]) {chmax(dp[e.first], dp[v] - e.second + A[e.first]);}}}for (int iter = 0; iter <= N; ++iter) {for (int v = 0; v < N; ++v) {if (dp[v] <= -INF/2) continue;for (auto e : G[v]) {if (chmax(dp[e.first], dp[v] - e.second + A[e.first])) {negative[e.first] = true;}if (negative[v]) negative[e.first] = true;}}//COUT(dp);}if (!negative[N-1]) cout << dp[N-1] << endl;else cout << "inf" << endl;}*/int main() {int H, W;cin >> H >> W;vector<string> A(H);for (int i = 0; i < H; ++i) cin >> A[i];vector dp(H, vector(W, vector(30, 0LL)));dp[0][0][1] = 1;long long res = 0;for (int i = 0; i < H; ++i) {for (int j = 0; j < W; ++j) {for (int k = 0; k < 29; ++k) {if (i == H-1 && j == W-1) res += dp[i][j][k];if (i+1 < H && A[i+1][j] != '#') {int add = (A[i+1][j] == 'o' ? 1 : -1);if (k + add >= 0) {dp[i+1][j][k+add] += dp[i][j][k];}}if (j+1 < W && A[i][j+1] != '#') {int add = (A[i][j+1] == 'o' ? 1 : -1);if (k + add >= 0) {dp[i][j+1][k+add] += dp[i][j][k];}}}}}cout << res << endl;}