You are given an array a_1, a_2, …, a_n.

You need to perform q queries of the following two types:

  1. "MULTIPLY l r x" — for every i (l ≤ i ≤ r) multiply a_i by x.
  2. "TOTIENT l r" — print \varphi(∏ _{i=l}^{r} a_i) taken modulo 10^9+7, where \varphi denotes Euler's totient function. 



The [Euler's totient function](http://gg.gg/euler_totient) of a positive integer n (denoted as \varphi(n)) is the number of integers x (1 ≤ x ≤ n) such that \gcd(n,x) = 1.

Input

The first line contains two integers n and q (1 ≤ n ≤ 4 ⋅ 10^5, 1 ≤ q ≤ 2 ⋅ 10^5) — the number of elements in array a and the number of queries.

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 300) — the elements of array a.

Then q lines follow, describing queries in the format given in the statement.

  1. "MULTIPLY l r x" (1 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 300) — denotes a multiplication query.
  2. "TOTIENT l r" (1 ≤ l ≤ r ≤ n) — denotes a query on the value of Euler's totient function. 



It is guaranteed that there is at least one "TOTIENT" query.

Output

For each "TOTIENT" query, print the answer to it.

Example

Input

4 4
5 9 1 2
TOTIENT 3 3
TOTIENT 3 4
MULTIPLY 4 4 3
TOTIENT 4 4


Output

1
1
2

Note

In the first example, \varphi(1) = 1 for the first query, \varphi(2) = 1 for the second query and \varphi(6) = 2 for the third one.
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
template <typename T>
struct modular {
  constexpr modular() : val(0) {}
  constexpr modular(const modular<T>& _m) : val(_m.val) {}
  template <typename U>
  constexpr modular(const U& _r = U()) {
    val = -MOD <= _r && _r < MOD ? _r : _r % MOD;
    if (val < 0) {
      val += MOD;
    }
  }
  const T operator()() { return val; }
  template <typename U>
  explicit operator U() const {
    return static_cast<U>(val);
  }
  modular<T>& operator+=(const modular<T>& _m) {
    if ((val += _m.val) >= MOD) {
      val -= MOD;
    }
    return *this;
  }
  modular<T>& operator-=(const modular<T>& _m) {
    if ((val -= _m.val) < 0) {
      val += MOD;
    }
    return *this;
  }
  modular<T>& operator*=(const modular<T>& _m) {
    val = modular<T>(static_cast<int64_t>(val) * static_cast<int64_t>(_m.val))
              .val;
    return *this;
  }
  modular<T>& operator/=(const modular<T>& _m) {
    T a = _m.val, b = MOD, u = 0, v = 1;
    while (a != 0) {
      T q = b / a;
      b -= q * a;
      swap(a, b);
      u -= q * v;
      swap(u, v);
    }
    return *this *= u;
  }
  modular<T>& operator=(const modular<T>& _m) {
    val = _m.val;
    return *this;
  }
  template <typename U>
  modular<T>& operator+=(const U& _r) {
    return *this += modular<T>(_r);
  }
  template <typename U>
  modular<T>& operator-=(const U& _r) {
    return *this -= modular<T>(_r);
  }
  template <typename U>
  modular<T>& operator*=(const U& _r) {
    return *this *= modular<T>(_r);
  }
  template <typename U>
  modular<T>& operator/=(const U& _r) {
    return *this /= modular<T>(_r);
  }
  template <typename U>
  modular<T>& operator=(const U& _r) {
    val = modular<T>(_r).val;
    return *this;
  }
  modular<T> operator-() { return modular<T>(-val); }
  template <typename U>
  friend bool operator==(const modular<U>&, const modular<U>&);
  friend std::istream& operator>>(std::istream& os, modular<T>& _m) {
    os >> _m.val;
    _m *= 1;
    return os;
  }
  friend std::ostream& operator<<(std::ostream& os, const modular<T>& _m) {
    return os << _m.val;
  }
  template <typename U>
  modular<T> exp(U e) {
    modular<T> res = 1;
    modular<T> b = val;
    if (e < 0) {
      b = 1 / b;
      e *= -1;
    }
    for (; e; e >>= 1) {
      if (e & 1) {
        res *= b;
      }
      b *= b;
    }
    return res;
  }

 private:
  T val;
};
template <typename T>
inline modular<T> operator+(const modular<T>& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) += _rhs;
}
template <typename T, typename U>
inline modular<T> operator+(const modular<T>& _lhs, const U& _rhs) {
  return modular<T>(_lhs) += _rhs;
}
template <typename T, typename U>
inline modular<T> operator+(const U& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) += _rhs;
}
template <typename T>
inline modular<T> operator-(const modular<T>& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) -= _rhs;
}
template <typename T, typename U>
inline modular<T> operator-(const modular<T>& _lhs, const U& _rhs) {
  return modular<T>(_lhs) -= _rhs;
}
template <typename T, typename U>
inline modular<T> operator-(const U& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) -= _rhs;
}
template <typename T>
inline modular<T> operator*(const modular<T>& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) *= _rhs;
}
template <typename T, typename U>
inline modular<T> operator*(const modular<T>& _lhs, const U& _rhs) {
  return modular<T>(_lhs) *= _rhs;
}
template <typename T, typename U>
inline modular<T> operator*(const U& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) *= _rhs;
}
template <typename T>
inline modular<T> operator/(const modular<T>& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) /= _rhs;
}
template <typename T, typename U>
inline modular<T> operator/(const modular<T>& _lhs, const U& _rhs) {
  return modular<T>(_lhs) /= _rhs;
}
template <typename T, typename U>
inline modular<T> operator/(const U& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) /= _rhs;
}
template <typename T>
inline bool operator==(const modular<T>& _lhs, const modular<T>& _rhs) {
  return _lhs.val == _rhs.val;
}
template <typename T, typename U>
inline bool operator==(const modular<T>& _lhs, const U& _rhs) {
  return _lhs == modular<T>(_rhs);
}
template <typename T, typename U>
inline bool operator==(const U& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) == _rhs;
}
template <typename T>
inline bool operator!=(const modular<T>& _lhs, const modular<T>& _rhs) {
  return !(_lhs == _rhs);
}
template <typename T, typename U>
inline bool operator!=(const modular<T>& _lhs, const U& _rhs) {
  return !(_lhs == _rhs);
}
template <typename T, typename U>
inline bool operator!=(const U& _lhs, const modular<T>& _rhs) {
  return !(_lhs == _rhs);
}
struct Sieve {
  int sz;
  vector<bool> is;
  vector<int> prime;
  Sieve(int n = 45000) : sz(n) {
    prime.reserve(n / 6);
    is.assign(n + 1, true);
    is[0] = is[1] = false;
    for (int p = 2; (int64_t)p * p <= n; p++) {
      if (is[p]) {
        for (int i = p * p; i <= n; i += p) {
          is[i] = false;
        }
      }
    }
    for (int i = 2; i <= n; i++) {
      if (is[i]) prime.emplace_back(i);
    }
  }
  vector<pair<int, int>> factor(int x) {
    assert(x > 0 && (int64_t)sz * sz >= x);
    vector<pair<int, int>> res;
    for (const int& p : prime) {
      if ((int64_t)p * p > x) break;
      if (x % p == 0) {
        int e = 0;
        while (x % p == 0) {
          e++;
          x /= p;
        }
        res.emplace_back(p, e);
      }
    }
    if (x != 1) res.emplace_back(x, 1);
    return res;
  }
  vector<int> divs(int x, bool sorted = false) {
    vector<int> res;
    res.emplace_back(1);
    for (auto& p : factor(x)) {
      int b, e;
      tie(b, e) = p;
      int sz = res.size();
      int y = 1;
      while (e--) {
        y *= b;
        for (int i = 0; i < sz; i++) {
          res.emplace_back(res[i] * y);
        }
      }
    }
    if (sorted) sort(res.begin(), res.end());
    return res;
  }
  int num_divs(int x) {
    int res = 1;
    for (auto& pe : factor(x)) {
      res *= (1 + pe.second);
    }
    return res;
  }
  bool is_prime(int x) {
    if (x <= sz) return is[x];
    return factor(x)[0].first == x;
  }
  vector<int> p_divs(int x) {
    assert(x > 0 && (int64_t)sz * sz >= x);
    vector<int> res;
    for (const int& p : prime) {
      if ((int64_t)p * p > x) break;
      if (x % p == 0) {
        while (x % p == 0) {
          x /= p;
        }
        res.emplace_back(p);
      }
    }
    if (x != 1) res.emplace_back(x);
    return res;
  }
};
template <typename M, typename D>
struct SegLazy {
  using Op = function<M(const M&, const M&)>;
  using D2M = function<void(M&, const D&)>;
  using D2D = function<void(D&, const D&)>;
  M ID;
  D UN;
  Op op;
  D2M d2m;
  D2D d2d;
  int N, L;
  vector<M> a;
  vector<D> d;
  SegLazy(int n, M leaf_default, M _ID, D _UN, Op _op, D2M _d2m, D2D _d2d)
      : ID(_ID), UN(_UN), op(_op), d2m(_d2m), d2d(_d2d) {
    init_space(n);
    fill(a.begin() + N, a.begin() + N + n, leaf_default);
    build();
  }
  SegLazy(const vector<M>& leaves, M _ID, D _UN, Op _op, D2M _d2m, D2D _d2d)
      : ID(_ID), UN(_UN), op(_op), d2m(_d2m), d2d(_d2d) {
    int n = leaves.size();
    init_space(n);
    copy(leaves.begin(), leaves.end(), a.begin() + N);
    build();
  }
  void init_space(int n) {
    N = 1;
    L = 0;
    while (N < n) N <<= 1, L++;
    a.assign(N << 1, ID);
    d.assign(N, UN);
  }
  inline void pull(int i) { a[i] = op(a[i << 1], a[i << 1 | 1]); }
  void build() {
    for (int i = N - 1; i >= 1; i--) pull(i);
  }
  inline int len(int i) { return 1 << (L + __builtin_clz(i) - 31); }
  inline void apply(int i, const D& dval) {
    d2m(a[i], dval);
    if (i < N) d2d(d[i], dval);
  }
  inline void push(int i) {
    apply(i << 1, d[i]);
    apply(i << 1 | 1, d[i]);
    d[i] = UN;
  }
  void update(int l, int r, const D& dval, int i, int sl, int sr) {
    if (r <= sl || sr <= l) return;
    if (l <= sl && sr <= r) return apply(i, dval);
    int sm = (sl + sr) >> 1, il = i << 1, ir = i << 1 | 1;
    push(i);
    update(l, r, dval, il, sl, sm);
    update(l, r, dval, ir, sm, sr);
    pull(i);
  }
  M query(int l, int r, int i, int sl, int sr) {
    if (r <= sl || sr <= l) return ID;
    if (l <= sl && sr <= r) return a[i];
    push(i);
    int sm = (sl + sr) >> 1, il = i << 1, ir = i << 1 | 1;
    return op(query(l, r, il, sl, sm), query(l, r, ir, sm, sr));
  }
  void update(int l, int r, const D& dval) {
    assert(0 <= l && r <= N);
    update(l, r, dval, 1, 0, N);
  }
  void assign(int p, const M& x) {
    assert(0 <= p && p < N);
    p += N;
    for (int k = L; k >= 1; k--) push(p >> k);
    for (a[p] = x; p >>= 1;) pull(p);
  }
  M query(int l, int r) {
    assert(0 <= l && r <= N);
    return query(l, r, 1, 0, N);
  }
  M query_point(int p) {
    assert(0 <= p && p < N);
    p += N;
    for (int k = L; k >= 1; k--) push(p >> k);
    return a[p];
  }
  M query_all() const { return a[1]; }
};
const int N = 300;
using ll = long long;
ll token[N + 1];
int kth[N + 1];
modular<int> coeff[62];
void prep() {
  Sieve s(N);
  {
    int cnt = 0;
    for (int p : s.prime) {
      kth[p] = cnt;
      coeff[cnt] = 1 - modular<int>(1) / p;
      cnt++;
    }
  }
  for (int i = 2; i <= N; i++) {
    for (auto& p : s.p_divs(i)) {
      token[i] |= 1ll << kth[p];
    }
  }
}
void solve() {
  prep();
  int n, q;
  cin >> n >> q;
  struct Prod {
    modular<int> x;
    int sz;
    Prod() {}
    Prod(modular<int> _x, int _sz) : x(_x), sz(_sz) {}
  };
  vector<Prod> a(n);
  vector<ll> b(n);
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    a[i] = {x, 1};
    b[i] = token[x];
  }
  SegLazy<Prod, modular<int>> prod(
      a, {1, 1}, 1,
      [](Prod u, Prod v) {
        return Prod{u.x * v.x, u.sz + v.sz};
      },
      [](Prod& u, modular<int> x) { u.x *= x.exp(u.sz); },
      [](modular<int>& x, modular<int> y) { x *= y; });
  SegLazy<ll, ll> occur(
      b, 0, 0, [](ll u, ll v) { return u | v; }, [](ll& u, ll x) { u |= x; },
      [](ll& x, ll y) { x |= y; });
  while (q--) {
    string op;
    cin >> op;
    if (op[0] == 'M') {
      int l, r, x;
      cin >> l >> r >> x;
      l--;
      prod.update(l, r, x);
      occur.update(l, r, token[x]);
    } else {
      int l, r;
      cin >> l >> r;
      l--;
      auto P = prod.query(l, r).x;
      auto t = occur.query(l, r);
      for (int i = 0; i < 62; i++) {
        if (t >> i & 1) P *= coeff[i];
      }
      cout << P << "\n";
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve();
  return 0;
}
