description: You are given n dominoes. Each domino has a left and a right cell. Each cell can be colored either black or white. Some cells are already colored, while some aren't yet.
  
  The coloring is said to be valid if and only if it is possible to rearrange the dominoes in some order such that for each 1 ≤ i ≤ n the color of the right cell of the i-th domino is different from the color of the left cell of the ((i mod n)+1)-st domino. 
  
  Note that you can't rotate the dominoes, so the left cell always remains the left cell, and the right cell always remains the right cell.
  
  Count the number of valid ways to color the yet uncolored cells of dominoes. Two ways are considered different if there is a cell that is colored white in one way and black in the other. In particular, colorings BW WB and WB BW different (and both invalid).
  
  As this number can be very big, output it modulo 998 244 353.
  
  Input
  
  The first line of the input contains a single integer n (1 ≤ n ≤ 10^5) — the number of dominoes.
  
  The next n lines describe dominoes. Each line contains two characters which represent the left and the right cell. Character B means that the corresponding cell is black, character W means that the corresponding cell is white, and ? means that the cell is yet to be colored. 
  
  Output
  
  Print a single integer — the answer to the problem.
  
  Examples
  
  Input
  
  
  1
  ?W
  
  
  Output
  
  
  1
  
  
  Input
  
  
  2
  ??
  W?
  
  
  Output
  
  
  2
  
  
  Input
  
  
  4
  BB
  ??
  W?
  ??
  
  
  Output
  
  
  10
  
  Note
  
  In the first test case, there is only one domino, and we need the color of its right cell to be different from the color of its left cell. There is only one way to achieve this.
  
  In the second test case, there are only 2 such colorings:
  
  BB WW and WB WB.
solution: #include <bits/stdc++.h>
  const double pi = acos(-1.0);
  typedef const double &cd;
  typedef const unsigned &cst;
  typedef const unsigned int &cu;
  typedef unsigned int *pu;
  typedef const unsigned int *cpu;
  struct cp {
    double a, b;
    __inline__ __attribute__((always_inline)) cp() {}
    __inline__ __attribute__((always_inline)) cp(cd x, cd y) : a(x), b(y) {}
    __inline__ __attribute__((always_inline)) cp operator+(const cp &o) const {
      return cp(a + o.a, b + o.b);
    }
    __inline__ __attribute__((always_inline)) cp operator-(const cp &o) const {
      return cp(a - o.a, b - o.b);
    }
    __inline__ __attribute__((always_inline)) cp operator*(const cp &o) const {
      return cp(a * o.a - b * o.b, b * o.a + a * o.b);
    }
    __inline__ __attribute__((always_inline)) cp operator*(cd o) const {
      return cp(a * o, b * o);
    }
    __inline__ __attribute__((always_inline)) cp operator!() const {
      return cp(a, -b);
    }
  };
  typedef cp *pcp;
  typedef const cp *cpcp;
  namespace cpoly {
  __inline__ __attribute__((always_inline)) void fft(const pcp &x, cst k,
                                                     const pcp &w) {
    if (__builtin_expect((k == 1), 0)) return;
    for (unsigned int i = 0, j = 0; i < k; ++i) {
      if (i > j) std::swap(x[i], x[j]);
      for (unsigned int l = k >> 1; (j ^= l) < l; l >>= 1)
        ;
    }
    w[0] = cp(1, 0);
    const cpcp xk = x + k;
    {
      for (cp *a = x, *b = x + 1; a < xk; a += 2, b += 2) {
        const cp o = *b;
        *b = *a - o;
        *a = *a + o;
      }
    }
    for (unsigned int i = 2; i < k; i <<= 1) {
      const cp g = cp(std::cos(pi / i), std::sin(pi / i));
      for (unsigned int j = i; j -= 2; w[j | 1] = (w[j] = w[j >> 1]) * g)
        ;
      w[1] = g;
      for (cp *a = x, *b = x + i; a < xk; a += i, b += i) {
        const cp *wl = w;
        for (const pcp c = b; a < c; ++a, ++b, ++wl) {
          const cp o = *b * *wl;
          *b = *a - o;
          *a = *a + o;
        }
      }
    }
  }
  __inline__ __attribute__((always_inline)) void ifft(const pcp &x, cst k,
                                                      const pcp &w) {
    if (__builtin_expect((k == 1), 0)) return;
    for (unsigned int i = 0, j = 0; i < k; i++) {
      if (i > j) std::swap(x[i], x[j]);
      for (unsigned int l = k >> 1; (j ^= l) < l; l >>= 1)
        ;
    }
    w[0] = cp(1, 0);
    const cpcp xk = x + k;
    {
      for (cp *a = x, *b = x + 1; a < xk; a += 2, b += 2) {
        const cp o = *b;
        *b = *a - o;
        *a = *a + o;
      }
    }
    for (unsigned int i = 2; i < k; i <<= 1) {
      const cp g = cp(std::cos(pi / i), -std::sin(pi / i));
      for (unsigned int j = i; j -= 2; w[j | 1] = (w[j] = w[j >> 1]) * g)
        ;
      w[1] = g;
      for (cp *a = x, *b = x + i; a < xk; a += i, b += i) {
        cp *wl = w;
        for (const pcp c = b; a < c; ++a, ++b, ++wl) {
          const cp o = *b * *wl;
          *b = *a - o;
          *a = *a + o;
        }
      }
    }
    for (unsigned int i = 0; i < k; i++) x[i] = cp(x[i].a / k, x[i].b / k);
  }
  }  // namespace cpoly
  namespace zpoly {
  using cpoly::fft;
  using cpoly::ifft;
  using std::memcpy;
  using std::memset;
  __inline__ __attribute__((always_inline)) void times(const cpu &a, const cpu &b,
                                                       const pu &c, cu n, cu m) {
    unsigned int l = (n + m) >> 1, len = 1;
    for (; len <= l; len <<= 1)
      ;
    cp *x = new cp[len], *y = new cp[len];
    {
      cp *ed = x + (n >> 1);
      const unsigned int *ai = a;
      for (cp *i = x; i < ed; ++ai, ++i) {
        i->a = *ai;
        i->b = *++ai;
      }
      ed->a = *ai;
      ed->b = (n & 1) ? *++ai : 0;
      const pcp xk = x + len - 1;
      if (__builtin_expect((ed < xk), 1))
        memset(ed + 1, 0, (xk - ed) * sizeof(cp));
    }
    {
      cp *ed = y + (m >> 1);
      const unsigned int *bi = b;
      for (cp *i = y; i < ed; ++bi, ++i) {
        i->a = *bi;
        i->b = *++bi;
      }
      ed->a = *bi;
      ed->b = (m & 1) ? *++bi : 0;
      const pcp yk = y + len - 1;
      if (__builtin_expect((ed < yk), 1))
        memset(ed + 1, 0, (yk - ed) * sizeof(cp));
    }
    cp *w = new cp[len];
    fft(x, len, w);
    fft(y, len, w);
    unsigned int hl = len >> 1;
    x[0] = x[0] * y[0] + cp(x[0].b * y[0].b * 2, 0);
    if (len > 1) {
      x[hl] = x[hl] * y[hl];
      for (unsigned int i = 1, j; i < hl; ++i) {
        j = len - i;
        const cp tmp = x[i] * y[i] -
                       (x[i] - !x[j]) * (y[i] - !y[j]) * (w[i] + cp(1, 0)) * 0.25;
        x[j] = x[j] * y[j] - (x[j] - !x[i]) * (y[j] - !y[i]) *
                                 (cp(1, 0) - w[j ^ len >> 1]) * 0.25;
        x[i] = tmp;
      }
    }
    ifft(x, len, w);
    unsigned int *now = c + (n + m);
    if ((n + m) & 1) {
      *now = unsigned int(x[l].b + 0.5);
      --now;
    }
    *now = unsigned int(x[l].a + 0.5);
    for (const cp *i = x + l; --i >= x;) {
      *--now = unsigned int(i->b + 0.5);
      *--now = unsigned int(i->a + 0.5);
    }
  }
  __inline__ __attribute__((always_inline)) void times_eq(const pu &a,
                                                          const cpu &b, cu n,
                                                          cu m) {
    unsigned int l = (n + m) >> 1, len = 1;
    for (; len <= l; len <<= 1)
      ;
    cp *x = new cp[len], *y = new cp[len];
    {
      cp *ed = x + (n >> 1);
      const unsigned int *ai = a;
      for (cp *i = x; i < ed; ++ai, ++i) {
        i->a = *ai;
        i->b = *++ai;
      }
      ed->a = *ai;
      ed->b = (n & 1) ? *++ai : 0;
      const pcp xk = x + len - 1;
      if (__builtin_expect((ed < xk), 1))
        memset(ed + 1, 0, (xk - ed) * sizeof(cp));
    }
    {
      cp *ed = y + (m >> 1);
      const unsigned int *bi = b;
      for (cp *i = y; i < ed; ++bi, ++i) {
        i->a = *bi;
        i->b = *++bi;
      }
      ed->a = *bi;
      ed->b = (m & 1) ? *++bi : 0;
      const pcp yk = y + len - 1;
      if (__builtin_expect((ed < yk), 1))
        memset(ed + 1, 0, (yk - ed) * sizeof(cp));
    }
    cp *w = new cp[len];
    fft(x, len, w);
    fft(y, len, w);
    unsigned int hl = len >> 1;
    x[0] = x[0] * y[0] + cp(x[0].b * y[0].b * 2, 0);
    if (len > 1) {
      x[hl] = x[hl] * y[hl];
      for (unsigned int i = 1, j; i < hl; ++i) {
        j = len - i;
        const cp tmp = x[i] * y[i] -
                       (x[i] - !x[j]) * (y[i] - !y[j]) * (w[i] + cp(1, 0)) * 0.25;
        x[j] = x[j] * y[j] - (x[j] - !x[i]) * (y[j] - !y[i]) *
                                 (cp(1, 0) - w[j ^ len >> 1]) * 0.25;
        x[i] = tmp;
      }
    }
    ifft(x, len, w);
    unsigned int *now = a + (n + m);
    if ((n + m) & 1) {
      *now = unsigned int(x[l].b + 0.5);
      --now;
    }
    *now = unsigned int(x[l].a + 0.5);
    for (const cp *i = x + l; --i >= x;) {
      *--now = unsigned int(i->b + 0.5);
      *--now = unsigned int(i->a + 0.5);
    }
  }
  }  // namespace zpoly
  namespace f_998244353_poly {
  using std::memcpy;
  using std::memset;
  __inline__ __attribute__((always_inline)) unsigned long long quickpow(
      unsigned long long x, unsigned int k, unsigned long long ret = 1) {
    for (; k; k >>= 1, x = x * x % 998244353)
      if (k & 1) ret = ret * x % 998244353;
    return ret;
  }
  inline void mod1(unsigned int &x) { x >= 998244353 && (x -= 998244353); }
  inline void mod2(unsigned int &x) { int(x) < 0 && (x += 998244353); }
  inline void getw(const pu &w, cu l) {
    for (unsigned int i = l >> 1, wi; i; w[i >>= 1] = wi)
      wi = quickpow(3, 499122176 / i);
    for (unsigned int i = 1, ed = l >> 1; i < ed; i <<= 1) {
      const cpu c = w + i;
      const unsigned long long wi = *c;
      for (pu a = w, b = w + i; (++b, ++a) < c; *b = *a * wi % 998244353)
        ;
    }
    w[0] = 1;
  }
  inline void getiw_with_w(const pu &w, cu l) {
    if (l >= 4) {
      w[1] = 998244353 - w[1];
      for (unsigned int i = 2, ed = l >> 1; i < ed; i <<= 1)
        for (pu a = w + i, b = w + (i << 1); --b > a; ++a) {
          const unsigned int o = *a;
          *a = 998244353 - *b;
          *b = 998244353 - o;
        }
    }
  }
  inline void ntt_with_w(const pu &x, cu l, const cpu &w) {
    const cpu xl = x + l;
    for (unsigned int i = l; i >>= 1;) {
      cpu wl = w;
      for (pu a = x, b = x + i; a < xl; a += i, b += i, ++wl) {
        const unsigned long long w = *wl;
        for (const cpu c = b; a < c; ++a, ++b) {
          const unsigned int o = *b * w % 998244353;
          mod2(*b = *a - o);
          mod1(*a += o);
        }
      }
    }
  }
  inline void intt_with_iw(const pu &x, cu l, const cpu &w) {
    const cpu xl = x + l;
    for (unsigned int i = 1; i < l; i <<= 1) {
      cpu wl = w;
      for (pu a = x, b = x + i; a < xl; a += i, b += i, ++wl) {
        const unsigned long long w = *wl;
        for (const cpu c = b; a < c; ++a, ++b) {
          const unsigned int o = *b;
          *b = (*a - o + 998244353) * w % 998244353;
          mod1(*a += o);
        }
      }
    }
    unsigned long long iv = quickpow(l, 998244351);
    for (unsigned int *i = x + l; --i >= x; *i = *i * iv % 998244353)
      ;
  }
  inline void ntt(const pu &x, cu l, const pu &w) {
    getw(w, l);
    ntt_with_w(x, l, w);
  }
  inline void intt(const pu &x, cu l, const pu &w) {
    getw(w, l);
    getiw_with_w(w, l);
    intt_with_iw(x, l, w);
  }
  __inline__ __attribute__((always_inline)) unsigned int getl(unsigned int l) {
    if (__builtin_expect((!l), 0))
      l = 1;
    else {
      for (unsigned int tmp; (tmp = l & (l - 1)); l = tmp)
        ;
      l <<= 1;
    }
    return l;
  }
  __inline__ __attribute__((always_inline)) void times_eq_non_const_wel_small_1(
      const pu &a, const pu &b, cu l) {
    const pu w = new unsigned int[l];
    getw(w, l);
    ntt_with_w(a, l, w);
    ntt_with_w(b, l, w);
    for (unsigned int *ai = a + l, *bi = b + l; (--bi, --ai) >= a;
         *ai = unsigned long long(*ai) * *bi % 998244353)
      ;
    getiw_with_w(w, l);
    intt_with_iw(a, l, w);
    delete[] w;
  }
  __inline__ __attribute__((always_inline)) void times_eq_non_const_wel_small(
      const pu &a, const pu &b, cu n, cu m, cu l) {
    memset(a + n + 1, 0, (l - n - 1) << 2);
    memset(b + m + 1, 0, (l - m - 1) << 2);
    times_eq_non_const_wel_small_1(a, b, l);
  }
  __inline__ __attribute__((always_inline)) void times_eq_non_const_wel_small(
      const pu &a, const pu &b, cu n, cu m) {
    times_eq_non_const_wel_small(a, b, n, m, getl(n + m));
  }
  __inline__ __attribute__((always_inline)) void times_non_const_wel_small(
      const pu &a, const pu &b, const pu &c, cu n, cu m, cu l) {
    times_eq_non_const_wel_small(a, b, n, m, l);
    memcpy(c, a, (n + m + 1) << 2);
  }
  __inline__ __attribute__((always_inline)) void times_non_const_wel_small(
      const pu &a, const pu &b, const pu &c, cu n, cu m) {
    times_non_const_wel_small(a, b, c, n, m, getl(n + m));
  }
  template <typename T_iita, typename T_iitb, typename T_oitc>
  __inline__ __attribute__((always_inline)) void times_big(cu n, cu m,
                                                           T_iita &iita,
                                                           T_iitb &iitb,
                                                           T_oitc &oitc) {
    unsigned int nb = n / 4194304, mb = m / 4194304;
    const pu a = new unsigned int[(nb + 1) * 8388608],
             b = new unsigned int[(mb + 1) * 8388608];
    const pu w = new unsigned int[8388608];
    getw(w, 8388608);
    const pu anb = a + nb * 8388608, bmb = b + mb * 8388608;
    {
      const pu an = a + ((n << 1) - n % 4194304);
      unsigned int *x = a;
      for (; (x + 4194304) <= an; x += 4194304) {
        for (const pu ed = x + 4194304; x < ed; ++x, ++iita) *x = *iita;
        memset(x, 0, 4194304 << 2);
        ntt_with_w(x - 4194304, 8388608, w);
      }
      for (; x <= an; ++x, ++iita) *x = *iita;
      memset(x, 0, 8388608 - (x - anb));
      ntt_with_w(anb, 8388608, w);
    }
    {
      const pu bm = b + ((m << 1) - m % 4194304);
      unsigned int *x = b;
      for (; (x + 4194304) <= bm; x += 4194304) {
        for (const pu ed = x + 4194304; x < ed; ++x, ++iitb) *x = *iitb;
        memset(x, 0, 4194304 << 2);
        ntt_with_w(x - 4194304, 8388608, w);
      }
      for (; x <= bm; ++x, ++iitb) *x = *iitb;
      memset(x, 0, 8388608 - (x - bmb));
      ntt_with_w(bmb, 8388608, w);
    }
    const pu now = new unsigned int[8388608], prv = new unsigned int[4194304];
    memset(prv, 0, 4194304 << 2);
    getiw_with_w(w, 8388608);
    if (nb <= mb) {
      for (unsigned int i = 0; i <= nb; ++i) {
        memset(now, 0, 8388608 << 2);
        for (unsigned int *x = a, *y = b + i * 8388608; y >= b; y -= 8388608 << 1)
          for (pu ed = x + 8388608, t = now; x < ed; ++x, ++y, ++t)
            *t = (*t + unsigned long long(*x) * *y) % 998244353;
        intt_with_iw(now, 8388608, w);
        for (unsigned int i = 0; i < 4194304; ++i, ++oitc) {
          unsigned int x = now[i] + prv[i];
          mod1(x);
          *oitc = x;
        }
        memcpy(prv, now + 4194304, 4194304 << 2);
      }
      if (__builtin_expect((nb), 1)) {
        for (unsigned int i = 1, ed = mb - nb; i <= ed; ++i) {
          memset(now, 0, 8388608 << 2);
          for (unsigned int *x = anb, *y = b + i * 8388608; x >= a;
               x -= 8388608 << 1)
            for (pu ed = x + 8388608, t = now; x < ed; ++x, ++y, ++t)
              *t = (*t + unsigned long long(*x) * *y) % 998244353;
          intt_with_iw(now, 8388608, w);
          for (unsigned int i = 0; i < 4194304; ++i, ++oitc) {
            unsigned int x = now[i] + prv[i];
            mod1(x);
            *oitc = x;
          }
          memcpy(prv, now + 4194304, 4194304 << 2);
        }
        for (unsigned int i = nb; --i;) {
          memset(now, 0, 8388608 << 2);
          for (unsigned int *x = anb - i * 8388608, *y = bmb; x <= anb;
               y -= 8388608 << 1)
            for (pu ed = x + 8388608, t = now; x < ed; ++x, ++y, ++t)
              *t = (*t + unsigned long long(*x) * *y) % 998244353;
          intt_with_iw(now, 8388608, w);
          for (unsigned int i = 0; i < 4194304; ++i, ++oitc) {
            unsigned int x = now[i] + prv[i];
            mod1(x);
            *oitc = x;
          }
          memcpy(prv, now + 4194304, 4194304 << 2);
        }
      } else {
        for (unsigned int i = 1, ed = mb - nb; i < ed; ++i) {
          memset(now, 0, 8388608 << 2);
          for (unsigned int *x = anb, *y = b + i * 8388608; x >= a;
               x -= 8388608 << 1)
            for (pu ed = x + 8388608, t = now; x < ed; ++x, ++y, ++t)
              *t = (*t + unsigned long long(*x) * *y) % 998244353;
          intt_with_iw(now, 8388608, w);
          for (unsigned int i = 0; i < 4194304; ++i, ++oitc) {
            unsigned int x = now[i] + prv[i];
            mod1(x);
            *oitc = x;
          }
          memcpy(prv, now + 4194304, 4194304 << 2);
        }
      }
      for (unsigned int *x = anb, *y = bmb, *t = now, *ed = anb + 8388608; x < ed;
           ++x, ++y, ++t)
        *t = unsigned long long(*x) * *y % 998244353;
      intt_with_iw(now, 8388608, w);
      unsigned int exl = n + m - 4194304 * (nb + mb);
      if (exl < 4194304) {
        for (unsigned int i = 0; i <= exl; ++i, ++oitc) {
          unsigned int x = now[i] + prv[i];
          mod1(x);
          *oitc = x;
        }
      } else {
        for (unsigned int i = 0; i < 4194304; ++i, ++oitc) {
          unsigned int x = now[i] + prv[i];
          mod1(x);
          *oitc = x;
        }
        for (unsigned int *i = now + 4194304, *ed = now + exl; i <= ed;
             ++i, ++oitc)
          *oitc = *i;
      }
    } else {
      for (unsigned int i = 0; i <= mb; ++i) {
        memset(now, 0, 8388608 << 2);
        for (unsigned int *x = b, *y = a + i * 8388608; y >= a; y -= 8388608 << 1)
          for (pu ed = x + 8388608, t = now; x < ed; ++x, ++y, ++t)
            *t = (*t + unsigned long long(*x) * *y) % 998244353;
        intt_with_iw(now, 8388608, w);
        for (unsigned int i = 0; i < 4194304; ++i, ++oitc) {
          unsigned int x = now[i] + prv[i];
          mod1(x);
          *oitc = x;
        }
        memcpy(prv, now + 4194304, 4194304 << 2);
      }
      if (__builtin_expect((mb), 1)) {
        for (unsigned int i = 1, ed = nb - mb; i <= ed; ++i) {
          memset(now, 0, 8388608 << 2);
          for (unsigned int *x = bmb, *y = a + i * 8388608; x >= b;
               x -= 8388608 << 1)
            for (pu ed = x + 8388608, t = now; x < ed; ++x, ++y, ++t)
              *t = (*t + unsigned long long(*x) * *y) % 998244353;
          intt_with_iw(now, 8388608, w);
          for (unsigned int i = 0; i < 4194304; ++i, ++oitc) {
            unsigned int x = now[i] + prv[i];
            mod1(x);
            *oitc = x;
          }
          memcpy(prv, now + 4194304, 4194304 << 2);
        }
        for (unsigned int i = mb; --i;) {
          memset(now, 0, 8388608 << 2);
          for (unsigned int *x = bmb - i * 8388608, *y = anb; x <= bmb;
               y -= 8388608 << 1)
            for (pu ed = x + 8388608, t = now; x < ed; ++x, ++y, ++t)
              *t = (*t + unsigned long long(*x) * *y) % 998244353;
          intt_with_iw(now, 8388608, w);
          for (unsigned int i = 0; i < 4194304; ++i, ++oitc) {
            unsigned int x = now[i] + prv[i];
            mod1(x);
            *oitc = x;
          }
          memcpy(prv, now + 4194304, 4194304 << 2);
        }
      } else {
        for (unsigned int i = 1, ed = nb - mb; i < ed; ++i) {
          memset(now, 0, 8388608 << 2);
          for (unsigned int *x = bmb, *y = a + i * 8388608; x >= b;
               x -= 8388608 << 1)
            for (pu ed = x + 8388608, t = now; x < ed; ++x, ++y, ++t)
              *t = (*t + unsigned long long(*x) * *y) % 998244353;
          intt_with_iw(now, 8388608, w);
          for (unsigned int i = 0; i < 4194304; ++i, ++oitc) {
            unsigned int x = now[i] + prv[i];
            mod1(x);
            *oitc = x;
          }
          memcpy(prv, now + 4194304, 4194304 << 2);
        }
      }
      for (unsigned int *x = bmb, *y = anb, *t = now, *ed = bmb + 8388608; x < ed;
           ++x, ++y, ++t)
        *t = unsigned long long(*x) * *y % 998244353;
      intt_with_iw(now, 8388608, w);
      unsigned int exl = n + m - 4194304 * (mb + nb);
      if (exl < 4194304) {
        for (unsigned int i = 0; i <= exl; ++i, ++oitc) {
          unsigned int x = now[i] + prv[i];
          mod1(x);
          *oitc = x;
        }
      } else {
        for (unsigned int i = 0; i < 4194304; ++i, ++oitc) {
          unsigned int x = now[i] + prv[i];
          mod1(x);
          *oitc = x;
        }
        for (unsigned int *i = now + 4194304, *ed = now + exl; i <= ed;
             ++i, ++oitc)
          *oitc = *i;
      }
    }
    delete[] w, delete[] now, delete[] prv;
  }
  __inline__ __attribute__((always_inline)) void times_big_fbstd(cu n, cu m) {
    using std::fread;
    using std::fwrite;
    unsigned int nb = n / 4194304, mb = m / 4194304;
    const pu a = new unsigned int[(nb + 1) * 8388608],
             b = new unsigned int[(mb + 1) * 8388608];
    const pu w = new unsigned int[8388608];
    getw(w, 8388608);
    const pu anb = a + nb * 8388608, bmb = b + mb * 8388608;
    {
      const pu an = a + ((n << 1) - n % 4194304);
      unsigned int *x = a;
      for (; (x + 4194304) <= an; x += 8388608) {
        fread(x, 4, 4194304, stdin);
        memset(x + 4194304, 0, 4194304 << 2);
        ntt_with_w(x, 8388608, w);
      }
      fread(x, 4, an - x + 1, stdin);
      memset(an + 1, 0, 8388608 - (an - x + 1));
      ntt_with_w(x, 8388608, w);
    }
    {
      const pu bm = b + ((m << 1) - m % 4194304);
      unsigned int *x = b;
      for (; (x + 4194304) <= bm; x += 8388608) {
        fread(x, 4, 4194304, stdin);
        memset(x + 4194304, 0, 4194304 << 2);
        ntt_with_w(x, 8388608, w);
      }
      fread(x, 4, bm - x + 1, stdin);
      memset(bm + 1, 0, 8388608 - (bm - x + 1));
      ntt_with_w(x, 8388608, w);
    }
    const pu now = new unsigned int[8388608], prv = new unsigned int[4194304];
    memset(prv, 0, 4194304 << 2);
    getiw_with_w(w, 8388608);
    if (nb <= mb) {
      for (unsigned int i = 0; i <= nb; ++i) {
        memset(now, 0, 8388608 << 2);
        for (unsigned int *x = a, *y = b + i * 8388608; y >= b; y -= 8388608 << 1)
          for (pu ed = x + 8388608, t = now; x < ed; ++x, ++y, ++t)
            *t = (*t + unsigned long long(*x) * *y) % 998244353;
        intt_with_iw(now, 8388608, w);
        for (unsigned int i = 0; i < 4194304; ++i) mod1(now[i] += prv[i]);
        fwrite(now, 4, 4194304, stdout);
        memcpy(prv, now + 4194304, 4194304 << 2);
      }
      if (__builtin_expect((nb), 1)) {
        for (unsigned int i = 1, ed = mb - nb; i <= ed; ++i) {
          memset(now, 0, 8388608 << 2);
          for (unsigned int *x = anb, *y = b + i * 8388608; x >= a;
               x -= 8388608 << 1)
            for (pu ed = x + 8388608, t = now; x < ed; ++x, ++y, ++t)
              *t = (*t + unsigned long long(*x) * *y) % 998244353;
          intt_with_iw(now, 8388608, w);
          for (unsigned int i = 0; i < 4194304; ++i) mod1(now[i] += prv[i]);
          fwrite(now, 4, 4194304, stdout);
          memcpy(prv, now + 4194304, 4194304 << 2);
        }
        for (unsigned int i = nb; --i;) {
          memset(now, 0, 8388608 << 2);
          for (unsigned int *x = anb - i * 8388608, *y = bmb; x <= anb;
               y -= 8388608 << 1)
            for (pu ed = x + 8388608, t = now; x < ed; ++x, ++y, ++t)
              *t = (*t + unsigned long long(*x) * *y) % 998244353;
          intt_with_iw(now, 8388608, w);
          for (unsigned int i = 0; i < 4194304; ++i) mod1(now[i] += prv[i]);
          fwrite(now, 4, 4194304, stdout);
          memcpy(prv, now + 4194304, 4194304 << 2);
        }
      } else {
        for (unsigned int i = 1, ed = mb - nb; i < ed; ++i) {
          memset(now, 0, 8388608 << 2);
          for (unsigned int *x = anb, *y = b + i * 8388608; x >= a;
               x -= 8388608 << 1)
            for (pu ed = x + 8388608, t = now; x < ed; ++x, ++y, ++t)
              *t = (*t + unsigned long long(*x) * *y) % 998244353;
          intt_with_iw(now, 8388608, w);
          for (unsigned int i = 0; i < 4194304; ++i) mod1(now[i] += prv[i]);
          fwrite(now, 4, 4194304, stdout);
          memcpy(prv, now + 4194304, 4194304 << 2);
        }
      }
      for (unsigned int *x = anb, *y = bmb, *t = now, *ed = anb + 8388608; x < ed;
           ++x, ++y, ++t)
        *t = unsigned long long(*x) * *y % 998244353;
      intt_with_iw(now, 8388608, w);
      unsigned int exl = n + m - 4194304 * (nb + mb);
      if (exl < 4194304) {
        for (unsigned int i = 0; i <= exl; ++i) mod1(now[i] += prv[i]);
        fwrite(now, 4, exl + 1, stdout);
      } else {
        for (unsigned int i = 0; i < 4194304; ++i) mod1(now[i] += prv[i]);
        fwrite(now, 4, exl + 1, stdout);
      }
    } else {
      for (unsigned int i = 0; i <= mb; ++i) {
        memset(now, 0, 8388608 << 2);
        for (unsigned int *x = b, *y = a + i * 8388608; y >= a; y -= 8388608 << 1)
          for (pu ed = x + 8388608, t = now; x < ed; ++x, ++y, ++t)
            *t = (*t + unsigned long long(*x) * *y) % 998244353;
        intt_with_iw(now, 8388608, w);
        for (unsigned int i = 0; i < 4194304; ++i) mod1(now[i] += prv[i]);
        fwrite(now, 4, 4194304, stdout);
        memcpy(prv, now + 4194304, 4194304 << 2);
      }
      if (__builtin_expect((mb), 1)) {
        for (unsigned int i = 1, ed = nb - mb; i <= ed; ++i) {
          memset(now, 0, 8388608 << 2);
          for (unsigned int *x = bmb, *y = a + i * 8388608; x >= b;
               x -= 8388608 << 1)
            for (pu ed = x + 8388608, t = now; x < ed; ++x, ++y, ++t)
              *t = (*t + unsigned long long(*x) * *y) % 998244353;
          intt_with_iw(now, 8388608, w);
          for (unsigned int i = 0; i < 4194304; ++i) mod1(now[i] += prv[i]);
          fwrite(now, 4, 4194304, stdout);
          memcpy(prv, now + 4194304, 4194304 << 2);
        }
        for (unsigned int i = mb; --i;) {
          memset(now, 0, 8388608 << 2);
          for (unsigned int *x = bmb - i * 8388608, *y = anb; x <= bmb;
               y -= 8388608 << 1)
            for (pu ed = x + 8388608, t = now; x < ed; ++x, ++y, ++t)
              *t = (*t + unsigned long long(*x) * *y) % 998244353;
          intt_with_iw(now, 8388608, w);
          for (unsigned int i = 0; i < 4194304; ++i) mod1(now[i] += prv[i]);
          fwrite(now, 4, 4194304, stdout);
          memcpy(prv, now + 4194304, 4194304 << 2);
        }
      } else {
        for (unsigned int i = 1, ed = nb - mb; i < ed; ++i) {
          memset(now, 0, 8388608 << 2);
          for (unsigned int *x = bmb, *y = a + i * 8388608; x >= b;
               x -= 8388608 << 1)
            for (pu ed = x + 8388608, t = now; x < ed; ++x, ++y, ++t)
              *t = (*t + unsigned long long(*x) * *y) % 998244353;
          intt_with_iw(now, 8388608, w);
          for (unsigned int i = 0; i < 4194304; ++i) mod1(now[i] += prv[i]);
          fwrite(now, 4, 4194304, stdout);
          memcpy(prv, now + 4194304, 4194304 << 2);
        }
      }
      for (unsigned int *x = bmb, *y = anb, *t = now, *ed = bmb + 8388608; x < ed;
           ++x, ++y, ++t)
        *t = unsigned long long(*x) * *y % 998244353;
      intt_with_iw(now, 8388608, w);
      unsigned int exl = n + m - 4194304 * (mb + nb);
      if (exl < 4194304) {
        for (unsigned int i = 0; i <= exl; ++i) mod1(now[i] += prv[i]);
        fwrite(now, 4, exl + 1, stdout);
      } else {
        for (unsigned int i = 0; i < 4194304; ++i) mod1(now[i] += prv[i]);
        fwrite(now, 4, exl + 1, stdout);
      }
    }
    delete[] w, delete[] now, delete[] prv;
  }
  __inline__ __attribute__((always_inline)) void inv_small(const cpu &a,
                                                           const pu &b, cu n,
                                                           cu m) {
    if (__builtin_expect((m == 1), 0))
      b[0] = quickpow(a[0], 998244351);
    else {
      unsigned int l = 2;
      for (; l < m; l <<= 1)
        ;
      const pu w = new unsigned int[l], iw = new unsigned int[l],
               f = new unsigned int[l], g = new unsigned int[l];
      b[0] = quickpow(a[0], 998244351);
      getw(w, l);
      memcpy(iw, w, (l >> 1) << 2);
      getiw_with_w(iw, l);
      for (l = 1;; l <<= 1) {
        const unsigned int dl = l << 1;
        if (dl <= n)
          memcpy(f, a, dl << 2);
        else {
          memcpy(f, a, (n + 1) << 2);
          memset(f + n + 1, 0, (dl - n - 1) << 2);
        }
        ntt_with_w(f, dl, w);
        memcpy(g, b, l << 2);
        memset(g + l, 0, l << 2);
        ntt_with_w(g, dl, w);
        for (unsigned int *fi = f + dl, *gi = g + dl; (--gi, --fi) >= f;
             *fi = unsigned long long(*fi) * *gi % 998244353)
          ;
        intt_with_iw(f, dl, iw);
        memset(f, 0, l << 2);
        ntt_with_w(f, dl, w);
        for (unsigned int *fi = f + dl, *gi = g + dl; (--gi, --fi) >= f;
             *fi = unsigned long long(*fi) * *gi % 998244353)
          ;
        intt_with_iw(f, dl, w);
        if (dl >= m) break;
        for (unsigned int i = l; i < dl; ++i)
          b[i] = __builtin_expect((f[i]), 1) ? 998244353 - f[i] : 0;
      }
      for (unsigned int i = l; i < m; ++i)
        b[i] = __builtin_expect((f[i]), 1) ? 998244353 - f[i] : 0;
      delete[] w, delete[] iw, delete[] f, delete[] g;
    }
  }
  __inline__ __attribute__((always_inline)) void derivative_eq(const pu &a,
                                                               cu n) {
    for (unsigned int *i = a + 1, *ed = a + n; i <= ed; ++i)
      *(i - 1) = unsigned long long(i - a) * *i % 998244353;
    a[n] = 0;
  }
  __inline__ __attribute__((always_inline)) void integration_eq(const pu &a,
                                                                cu n) {
    unsigned long long now = 1;
    for (unsigned int i = 2; i <= n; ++i)
      a[i] = a[i] * (now = now * i % 998244353) % 998244353;
    now = quickpow(now * (n + 1) % 998244353, 998244351);
    for (unsigned int i = n + 1; i; --i) {
      a[i] = a[i - 1] * now % 998244353;
      now = now * i % 998244353;
    }
    a[0] = 0;
  }
  __inline__ __attribute__((always_inline)) void ln_eq_non_const_wel_small(
      const pu &a, cu n, cu m) {
    if (__builtin_expect((!n), 0)) {
      memset(a, 0, (m + 1) << 2);
      return;
    }
    const unsigned int l = getl(n + m - 2);
    const pu b = new unsigned int[l];
    inv_small(a, b, n, m);
    derivative_eq(a, n);
    times_eq_non_const_wel_small(a, b, n - 1, m - 1, l);
    integration_eq(a, m - 1);
  }
  __inline__ __attribute__((always_inline)) void
  kth_derivative_value_eq_wel_small(const pu &a, cu n, cu p) {
    const unsigned int l = getl(n << 1);
    const pu b = new unsigned int[l];
    unsigned long long now = 1;
    for (unsigned int i = 2; i <= n; ++i)
      a[i] = a[i] * (now = now * i % 998244353) % 998244353;
    b[n] = now = quickpow(now, 998244353 - 2);
    for (unsigned int i = n; i; --i) b[i - 1] = now = now * i % 998244353;
    now = 1;
    for (unsigned int i = 1; i <= n; ++i)
      b[i] = b[i] * (now = now * p % 998244353) % 998244353;
    std::reverse(a, a + n + 1);
    times_eq_non_const_wel_small(a, b, n, n, l);
    std::reverse(a, a + n + 1);
    delete[] b;
  }
  __inline__ __attribute__((always_inline)) void taylor_series_eq_wel_small(
      const pu &a, cu n, cu p) {
    const unsigned int l = getl(n << 1);
    const pu b = new unsigned int[l];
    unsigned long long now = 1;
    for (unsigned int i = 2; i <= n; ++i)
      a[i] = a[i] * (now = now * i % 998244353) % 998244353;
    const unsigned int ifacn = b[n] = now = quickpow(now, 998244353 - 2);
    for (unsigned int i = n; i; --i) b[i - 1] = now = now * i % 998244353;
    now = 1;
    for (unsigned int i = 1; i <= n; ++i)
      b[i] = b[i] * (now = now * p % 998244353) % 998244353;
    std::reverse(a, a + n + 1);
    times_eq_non_const_wel_small(a, b, n, n, l);
    std::reverse(a, a + n + 1);
    a[n] = a[n] * (now = ifacn) % 998244353;
    for (unsigned int i = n, *j = a + n - 1; i; --i, --j)
      *j = *j * (now = now * i % 998244353) % 998244353;
    delete[] b;
  }
  __inline__ __attribute__((always_inline)) void division_eq_non_const_wel_small(
      const pu &a, const pu &b, cu n, cu m) {
    if (__builtin_expect((n < m), 0)) {
      a[0] = 0;
      return;
    }
    if (__builtin_expect((!m), 0)) {
      unsigned long long iv = quickpow(b[0], 998244353 - 2);
      for (pu i = a + n; i >= a; --i) *i = *i * iv % 998244353;
      return;
    }
    const unsigned int n1 = n - m;
    const unsigned int l = getl(n1 << 1);
    const pu c = new unsigned int[l];
    std::reverse(b, b + m + 1);
    inv_small(b, c, m, n1 + 1);
    std::reverse(a, a + n + 1);
    times_eq_non_const_wel_small(a, c, n1, n1, l);
    std::reverse(a, a + n1 + 1);
    delete[] c;
  }
  __inline__ __attribute__((always_inline)) void modulo_eq_non_const_wel_small(
      const pu &a, const pu &b, const pu &d, cu n, cu m) {
    if (__builtin_expect((n < m), 0)) {
      d[0] = 0;
      return;
    }
    if (__builtin_expect((!m), 0)) {
      unsigned long long iv = quickpow(b[0], 998244353 - 2);
      for (pu i = d + n, j = a + n; i >= d; --i, --j) *i = *j * iv % 998244353;
      a[0] = 0;
      return;
    }
    const unsigned int n1 = n - m;
    const unsigned int l1 = getl(n1 << 1);
    const pu c = new unsigned int[l1];
    std::reverse(b, b + m + 1);
    inv_small(b, c, m, n1 + 1);
    for (pu i = d, j = a + n, ed = d + n1; i <= ed; ++i, --j) *i = *j;
    times_eq_non_const_wel_small(d, c, n1, n1, l1);
    std::reverse(d, d + n1 + 1);
    std::reverse(b, b + m + 1);
    const unsigned int l2 = getl(n);
    const pu e = new unsigned int[l2];
    memcpy(e, d, (n1 + 1) << 2);
    times_eq_non_const_wel_small(b, e, m, n1, l2);
    if (__builtin_expect((m), 1))
      for (pu i = a + m - 1, j = b + m - 1; i >= a; --i, --j) mod2(*i -= *j);
    else
      a[0] = 0;
    delete[] c;
    delete[] e;
  }
  __inline__ __attribute__((always_inline)) void modulo_eq_non_const_wel_small(
      const pu &a, const pu &b, cu n, cu m) {
    if (__builtin_expect((n < m), 0)) return;
    if (__builtin_expect((!m), 0)) {
      a[0] = 0;
      return;
    }
    const unsigned int n1 = n - m;
    const unsigned int l1 = getl(n1 << 1);
    const unsigned int l2 = getl(n);
    const pu c = new unsigned int[l1];
    std::reverse(b, b + m + 1);
    inv_small(b, c, m, n1 + 1);
    const pu d = new unsigned int[std::max(l1, l2)];
    for (pu i = d, j = a + n, ed = d + n1; i <= ed; ++i, --j) *i = *j;
    times_eq_non_const_wel_small(d, c, n1, n1, l1);
    std::reverse(d, d + n1 + 1);
    std::reverse(b, b + m + 1);
    times_eq_non_const_wel_small(b, d, m, n1, l2);
    for (pu i = a + m - 1, j = b + m - 1; i >= a; --i, --j) mod2(*i -= *j);
    delete[] c;
    delete[] d;
  }
  }  // namespace f_998244353_poly
  using namespace std;
  using namespace f_998244353_poly;
  constexpr int max_n = 100000;
  constexpr int max_l = 1048576;
  unsigned int a[max_l];
  unsigned int b[max_l];
  unsigned int c[max_l];
  unsigned int w[max_l];
  unsigned int iw[max_l];
  int main() {
    int n;
    scanf("%d", &n);
    int now = 0, cnt1 = 0, cnt2 = 0, cnt3 = 0, ans = 1, ans1 = 1, ans2 = 1;
    for (int i = 1; i <= n; ++i) {
      char str[5];
      scanf("\n%s", str);
      if (str[1] == 'B')
        str[1] = 'W';
      else if (str[1] == 'W')
        str[1] = 'B';
      if (str[0] == str[1]) {
        if (str[0] == '?') ++cnt3, ++now, ans = ans * 2 % 998244353;
        if (str[0] == 'B')
          ans2 = 0;
        else if (str[0] == 'W')
          ans1 = 0;
      } else {
        if (str[0] == '?')
          if (str[1] == 'W')
            ++cnt1, ++now, ans1 = 0;
          else
            ++cnt2, ++now, ans2 = 0;
        else if (str[1] == '?')
          if (str[0] == 'B')
            ++cnt1, ++now, ans2 = 0;
          else
            ++cnt2, ++now, ans1 = 0;
        else {
          if (str[0] == 'B')
            --now;
          else
            ++now;
          ans = ans1 = ans2 = 0;
        }
      }
    }
    if (now < 0) {
      puts("0");
      return 0;
    }
    int l = f_998244353_poly::getl(n * 2);
    memset(a, 0, sizeof(a)), memset(b, 0, sizeof(b)), memset(c, 0, sizeof(c));
    a[1] = a[2] = 1;
    b[0] = b[1] = 1;
    c[0] = c[2] = 1, c[1] = 2;
    f_998244353_poly::getw(w, l);
    f_998244353_poly::ntt_with_w(a, l, w);
    f_998244353_poly::ntt_with_w(b, l, w);
    f_998244353_poly::ntt_with_w(c, l, w);
    for (int i = 0; i < l; ++i)
      a[i] = quickpow(a[i], cnt1) * quickpow(b[i], cnt2) % 998244353 *
             quickpow(c[i], cnt3) % 998244353;
    f_998244353_poly::getiw_with_w(w, l);
    intt_with_iw(a, l, w);
    printf("%llu\n",
           (998244353 * 10000ll + a[now] - ans + ans1 + ans2) % 998244353);
    return 0;
  }
  