TTPC 2019 L. 多項式の零点の個数

https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_l?lang=ja

Since $(x \bmod 10^K) = 0 \iff (x \bmod 2^K) = 0 \land (x \bmod 5^K) = 0$, we can use brute-force. I got TLE when using non-constexpr mod.

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()

using namespace std;
using ll = long long;

template<int MOD>
struct solver {
  class mint {
    int n;
  public:
    mint(int n_ = 0) : n(n_) {}
    explicit operator int() { return n; }
    friend mint operator-(mint a) { return -a.n + MOD * (a.n != 0); }
    friend mint operator+(mint a, mint b) { int x = a.n + b.n; return x - (x >= MOD) * MOD; }
    friend mint operator-(mint a, mint b) { int x = a.n - b.n; return x + (x < 0) * MOD; }
    friend mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
    friend mint &operator+=(mint &a, mint b) { return a = a + b; }
    friend mint &operator-=(mint &a, mint b) { return a = a - b; }
    friend mint &operator*=(mint &a, mint b) { return a = a * b; }
    friend bool operator==(mint a, mint b) { return a.n == b.n; }
    friend bool operator!=(mint a, mint b) { return a.n != b.n; }
    friend istream &operator>>(istream &i, mint &a) { return i >> a.n; }
    friend ostream &operator<<(ostream &o, mint a) { return o << a.n; }
  };

  mint modpow(mint a, long long b) {
    if (a == 0) return 0;
    mint res = 1;
    while (b > 0) {
      if (b & 1) res *= a;
      a *= a;
      b >>= 1;
    }
    return res;
  }

  string S;
  mint x;
  int k;

  solver(string S_) : S(S_) {}

  mint eval(mint x_) {
    k = S.size();
    x = x_;
    return f_expr();
  }

  mint f_expr() {
    mint r = f_term();
    if (k == 0 || (S[k - 1] != '+' && S[k - 1] != '-')) return r;
    char op = S[k - 1];
    k--;
    mint l = f_expr();
    if (op == '+') l += r; else l -= r;
    return l;
  }

  mint f_term() {
    mint r = f_factor();
    if (k == 0 || S[k - 1] != '*') return r;
    k--;
    mint l = f_term();
    return l * r;
  }

  mint f_factor() {
    if (isdigit(S[k - 1])) {
      int r = f_number();
      if (k == 0 || S[k - 1] != '^') return r % MOD;
      k--;
      mint l = f_value();
      return modpow(l, r);
    } else {
      return f_value();
    }
  }

  mint f_value() {
    if (S[k - 1] == ')') {
      k--;
      mint v = f_expr();
      assert(S[k - 1] == '(');
      k--;
      return v;
    } else if (S[k - 1] == 'x') {
      k--;
      return x;
    } else {
      return f_number() % MOD;
    }
  }

  int f_number() {
    int t = 1;
    int ans = 0;
    while (k > 0 && isdigit(S[k - 1])) {
      ans += (S[k - 1] - '0') * t;
      t *= 10;
      k--;
    }
    return ans;
  }
};

constexpr int power(int n, int k) {
  if (k == 0) return 1;
  return n * power(n, k - 1);
}

template<int K>
void solve(string S) {
  int ans2 = 0;
  int ans5 = 0;
  constexpr int two = power(2, K);
  constexpr int five = power(5, K);
  solver<two> solver2(S);
  solver<five> solver5(S);
  rep(i, two) if (solver2.eval(i) == 0) ans2 += 1;
  rep(i, five) if (solver5.eval(i) == 0) ans5 += 1;
  cout << ans2 * ans5 << endl;
}


int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int K; string S; cin >> K >> S;
  switch (K) {
    case 1: solve<1>(S); break;
    case 2: solve<2>(S); break;
    case 3: solve<3>(S); break;
    case 4: solve<4>(S); break;
    case 5: solve<5>(S); break;
    case 6: solve<6>(S); break;
    case 7: solve<7>(S); break;
    case 8: solve<8>(S); break;
    case 9: solve<9>(S); break;
  }
}