#include <bits/stdc++.h>

template <int m>
class ModInt {
    int raw_;

public:
    ModInt() : raw_(0) {}
    ModInt(const auto &v) : raw_(v % m) {}
    using mint = ModInt;
    using i64 = int64_t;
    mint &operator+=(const mint &rhs) {
        raw_ = (raw_ + rhs.raw_) % m;
        return *this;
    }
    mint &operator-=(const mint &rhs) {
        raw_ = (raw_ - rhs.raw_) % m;
        return *this;
    }
    mint &operator*=(const mint &rhs) {
        raw_ = (i64)raw_ * rhs.raw_ % m;
        return *this;
    }
    mint &operator/=(const mint &rhs) {
        raw_ = (i64)raw_ * qpow(rhs.raw_, m - 2) % m;
        return *this;
    }

    int value() const {
        return (raw_ + m) % m;
    }

    friend mint operator+(const mint &lhs, const mint &rhs) {
        return mint{lhs} += rhs;
    }
    friend mint operator-(const mint &lhs, const mint &rhs) {
        return mint{lhs} -= rhs;
    }
    friend mint operator*(const mint &lhs, const mint &rhs) {
        return mint{lhs} *= rhs;
    }
    friend mint operator/(const mint &lhs, const mint &rhs) {
        return mint{lhs} /= rhs;
    }

    static constexpr int qpow(int a, int b) {
        int res = 1;
        while (b) {
            if (b & 1) {
                res = (i64)res * a % m;
            }
            a = (i64)a * a % m, b >>= 1;
        }
        return res;
    }
};

template <typename T>
struct Matrix {
    std::vector<std::vector<T>> a{};

    Matrix() = default;
    explicit Matrix(int n) : a(n, std::vector<T>(n)) {}

    std::optional<Matrix> inv() const {
        int n = a.size();
        Matrix a(*this), b(I(n));

        for (int i = 0; i < n; ++i) {
            for (int j = i; j < n; ++j) {
                if (a.a[j][i].value()) {
                    if (j != i) {
                        std::swap(a.a[i], a.a[j]);
                        std::swap(b.a[i], b.a[j]);
                    }
                    break;
                }
            }

            if (!a.a[i][i].value()) {
                return std::nullopt;
            }

            {
                T iv = 1 / a.a[i][i];
                for (int j = 0; j < n; ++j) {
                    a.a[i][j] *= iv;
                    b.a[i][j] *= iv;
                }
            }

            for (int j = i + 1; j < n; ++j) {
                T f = a.a[j][i];
                for (int k = 0; k < n; ++k) {
                    a.a[j][k] -= a.a[i][k] * f;
                    b.a[j][k] -= b.a[i][k] * f;
                }
            }
        }

        for (int i = n - 1; i >= 0; --i) {
            for (int j = i - 1; j >= 0; --j) {
                T f = a.a[j][i];
                for (int k = 0; k < n; ++k) {
                    a.a[j][k] -= a.a[i][k] * f;
                    b.a[j][k] -= b.a[i][k] * f;
                }
            }
        }

        return b;
    };
    friend Matrix operator*(const Matrix &lhs, const Matrix &rhs) {
        int n = lhs.a.size();
        Matrix res(n);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < n; ++k) {
                    res.a[i][k] += lhs.a[i][j] * rhs.a[j][k];
                }
            }
        }
        return res;
    }
    friend Matrix operator+(const Matrix &lhs, const Matrix &rhs) {
        int n = lhs.a.size();
        Matrix res(n);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                res.a[i][j] = lhs.a[i][j] + rhs.a[i][j];
            }
        }
        return res;
    }
    static Matrix I(int n) {
        Matrix res(n);
        for (int i = 0; i < n; ++i) {
            res.a[i][i] = 1;
        }
        return res;
    }
};

template <typename T>
struct SparseMatrix {
    std::vector<std::pair<std::pair<int, int>, T>> items;
    using mat = Matrix<T>;
    SparseMatrix(const mat &dense) {
        int n = dense.a.size();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dense.a[i][j].value()) {
                    items.emplace_back(std::make_pair(i, j), dense.a[i][j]);
                }
            }
        }
    }
    friend mat operator*(const SparseMatrix &lhs, const mat &rhs) {
        int n = rhs.a.size();
        mat res(n);
        for (auto [p, v] : lhs.items) {
            auto [x, y] = p;
            for (int i = 0; i < n; ++i) {
                res.a[x][i] += v * rhs.a[y][i];
            }
        }
        return res;
    }
    friend mat operator*(const mat &lhs, const SparseMatrix &rhs) {
        int n = lhs.a.size();
        mat res(n);
        for (auto [p, v] : rhs.items) {
            auto [x, y] = p;
            for (int i = 0; i < n; ++i) {
                res.a[i][y] += lhs.a[i][x] * v;
            }
        }
        return res;
    }
};

using mint = ModInt<998244353>;
using mat = Matrix<mint>;
using smat = SparseMatrix<mint>;

constexpr int K = 41;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;

    std::string s;
    std::cin >> s;
    s = '#' + s;

    mat l = mat(2 * K), r = mat(2 * K);

    for (int order = 0; order < 2; ++order) {
        for (int i = 0; i < K; ++i) {
            for (int j = 0; j <= order; ++j) {
                l.a[i + j * K][i + order * K] = 1;
                r.a[i + j * K][i + order * K] = 1;
            }
            if (i + 1 < K) {
                if (i % 2 == 0) {
                    l.a[i][i + order * K + 1] = 1;
                } else {
                    r.a[i][i + order * K + 1] = 1;
                }
            }
        }
    }

    smat sparse_l = smat(l), sparse_r = smat(r);
    smat sparse_il = smat(l.inv().value()), sparse_ir = smat(r.inv().value());

    std::vector<mat> a(n + 1), ia(n + 1), sia(n + 1);
    a[0] = mat::I(2 * K);
    ia[0] = mat::I(2 * K);
    sia[0] = ia[0];
    for (int i = 1; i <= n; ++i) {
        if (s[i] == '(') {
            a[i] = a[i - 1] * sparse_l;
            ia[i] = sparse_il * ia[i - 1];
        } else {
            a[i] = a[i - 1] * sparse_r;
            ia[i] = sparse_ir * ia[i - 1];
        }
        sia[i] = sia[i - 1] + ia[i];
    }

    if (n >= 10) {
        return 0;
    }

    while (q--) {
        int op, l, r, k;
        std::cin >> op >> l >> r >> k;
        k *= 2;

        if (op == 1) {
            const mat &u = ia[l - 1], &v = a[r];
            auto get = [&](int x, int y) {
                mint res = 0;
                for (int i = 0; i < 2 * K; ++i) {
                    res += u.a[x][i] * v.a[i][y];
                }
                return res;
            };
            std::cout << get(0, k).value() << '\n';
        } else {
            const mat &v = a[r];
            auto get = [&](int x, int y) {
                mint res = 0;
                for (int i = 0; i < 2 * K; ++i) {
                    res += sia[r].a[x][i] * v.a[i][y];
                    if (l >= 2) {
                        res -= sia[l - 2].a[x][i] * v.a[i][y];
                    }
                }
                return res;
            };
            std::cout << get(0, k + K).value() << '\n';
        }
    }
}