struct DSU {
   vector<int> p;
   DSU(int n) : p(n, -1) {}
   int gp(int n) {
      if (p[n] < 0) return n;
      return p[n] = gp(p[n]);
   }
   void merge(int a, int b, int to_b = 0) {
      a = gp(a), b = gp(b);
      if (a == b) return;
      if (!to_b && size(a) > size(b)) swap(a, b);
      p[b] += p[a];
      p[a] = b;
   }
   bool is_merged(int a, int b) { return gp(a) == gp(b); }
   int size(int n) { return -p[gp(n)]; }
};
void solve() {
   int n, m, k, q;
   cin >> n >> m;
   DSU dsu(n);
   vvi edges(n);
   for (int i = 0, u, v; i < m; i++) {
      cin >> u >> v, u--, v--, edges[u].pb(v), edges[v].pb(u);
      dsu.merge(u, v);
   }
   cin >> k;
   vector<pi> xy(k);
   for (auto &[x, y]: xy) cin >> x >> y, x--, y--;
   cin >> q;
   // p, q 를 이어도 모든 xy에 대해 여전히 떨어져있을 수 있는가?
   // 처음에 xy 중 붙어있는게있으면 불가능하다.
   // 처음에는 모두 컴포넌트로 분리되어 있을 것이다.
   // p가 속한 컴포넌트와 q가 속한 컴포넌트가 이어졌을 때, 어떤 x[i], y[i]가 존재해 하나는 P에 하나는 Q에 있지 않으면 된다.
   // 컴포넌트별로 번호를 붙이고 (c1, c2) 같은 쌍들을 모두 모은다.
 
   int ok = 1;
   for (int i = 0; i < k; i++) {
      if (dsu.is_merged(xy[i].fi, xy[i].se)) ok = 0;
   }
 
   vector<set<int>> have(n);
   for (auto &[x, y]: xy) {
      x = dsu.gp(x);
      y = dsu.gp(y);
      have[x].insert(y);
      have[y].insert(x);
   }
 
   while (q--) {
      int p, q;
      cin >> p >> q, p--, q--;
      if (!ok) {
         cout << "No\n";
         continue;
      }
      if (dsu.is_merged(p, q)) {
         cout << "Yes\n";
         continue;
      }
      p = dsu.gp(p);
      q = dsu.gp(q);
      if (hass(have[p], q)) cout << "No\n";
      else cout << "Yes\n";
   }
}
 

bitset<MAX + 1> tmp;
int two[MAX + 1];
void solve() {
   sieve();
   two[0] = 1;
   for (int i = 1; i <= MAX; i++) two[i] = md(two[i - 1] * 2);
   int N;
   string S;
   cin >> N >> S;
   vi idx;
 
   for (int i = 0; i < N; i++)
      if (S[i] == '.') idx.pb(i);
   ll ans = 0;
 
   vi dp(N + 1);
   for (int M = 1; M < N; M++)
      if (N % M == 0) {
         tmp.reset();
         for (int i: idx) tmp[i % M] = 1;
         ll t = two[M - tmp.count()];
         dp[M] = t;
         for (int d = 1; d < M; d++) {
            if (M % d == 0) {
               dp[M] = md(dp[M] - dp[d]);
            }
         }
         ans = md(ans + dp[M]);
      }
   cout << ans;
}