#include <bits/stdc++.h>
using namespace std;

// boost
#include <boost/multiprecision/cpp_int.hpp>
using boost::multiprecision::cpp_int;

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;
using vld = vector<ld>;
using vvld = vector<vld>;

typedef pair<ll, ll> P;

#define bit(n) (1LL << (n))

//#define int long long

#define all(v) v.begin(), v.end()

#define rep(i, n) for (ll i = 0; i < n; i++)
#define REP(i, n) for (ll i = 1; i < n; i++)

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORm(i, m) for (auto i = m.begin(); i != m.end(); i++)

template <class T>
inline void chmax(T& a, T b) {
  a = std::max(a, b);
}
template <class T>
inline void chmin(T& a, T b) {
  a = std::min(a, b);
}

#define mod (ll)(1e9 + 7)
// #define mod (998244353ll)

const long long INF = 1LL << 60;

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);

  ll n, q;
  string s;
  cin >> n >> s >> q;
  vll vq(q);
  rep(i, q) cin >> vq[i];

  vll nc(n + 2);

  rep(i, n) {
    if (s[i] == 'C')
      nc[i]++;
  }

  REP(i, n) {
    nc[i] += nc[i - 1];
  }

  for (const auto k : vq) {
    ll ans = 0;

    vll imos(n + 2);
    vll dc(n + 2);

    rep(i, n) {
      if (s[i] == 'D') {
        dc[i] = nc[min(i + k - 1, n - 1)] - nc[i];
        imos[i]++;
        if (i + k < n) {
          imos[i + k]--;
        }
      }
    }

    REP(i, n) {
      imos[i] += imos[i - 1];
    }

    REP(i, n) {
      dc[i] += dc[i - 1];
      if (s[i] == 'C') {
        dc[i] -= imos[i];
      } else if (s[i] == 'M') {
        ans += dc[i];
      }
    }

    cout << ans << endl;
  }

  return 0;
}

#include<bits/stdc++.h>

int main(){
    using namespace std;
    constexpr unsigned long MOD = 998244353;

    string S;
    cin >> S;
    reverse(begin(S), end(S));
    unsigned long K;
    cin >> K;
    K = min<unsigned long>(count(begin(S), end(S), '1'), K);

    vector<vector<unsigned long>> dp(K + 1), tmp(K + 1);
    for(unsigned long i{0}; i <= K; ++i)dp[i] = vector(i + 1, 0UL);
    for(unsigned long i{0}; i <= K; ++i)tmp[i] = vector(i + 1, 0UL);
    dp[0][0] = 1;
    
    unsigned long cnt{0};
    for(const auto& c : S)if(c == '1')++cnt;
    else{
        for(auto&& i : tmp)fill(begin(i), end(i), 0UL);
        for(unsigned long i{0}; i < K; ++i)for(unsigned long j{0}; j + i < K; ++j){
            tmp[j + i + 1][i] = tmp[j + i][i] + dp[j + i][i];
            if(j >= cnt)tmp[j + i + 1][i] -= dp[j - cnt + i][i];
        }
        for(auto&& i : dp)partial_sum(begin(i), end(i), begin(i));
        for(unsigned long i{0}; i <= K; ++i)for(unsigned long j{0}; j <= i; ++j)(dp[i][j] += tmp[i][j]) %= MOD;
        cnt = 0;
    }
    for(auto&& i : dp)partial_sum(begin(i), end(i), begin(i));
    
    unsigned long ans{0};
    for(const auto& i : dp)ans += i.back();
    cout << ans % MOD << endl;
    return 0;
}