#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
int MAX_N = 30;
const int magic_const = 1e9 + 20;
const long long mod = 1e9 + 7;
const int LOG_NUM = 15;
class fenwick_tree {
  vector<long long> a;

 public:
  fenwick_tree(int n) { a.resize(n + 1); }
  void add(int pos, long long x) {
    for (pos++; pos < a.size(); pos += pos & -pos) {
      a[pos] += x;
    }
  }
  long long get(int pos) {
    long long answer = 0;
    for (pos++; pos > 0; pos -= pos & -pos) {
      answer += a[pos];
    }
    return answer;
  }
  long long get_sum(int left, int right) { return get(right) - get(left - 1); }
};
long long n, m;
int get_rand(int max_n) {
  return (int)(((rand() * (long long)RAND_MAX) + rand()) % max_n);
}
map<int, int> getters;
int tmp;
int get_ans(int tmp) {
  if (getters.find(tmp) != getters.end()) return getters[tmp];
  int ans;
  cout << "? " << tmp + 1 << endl;
  cin >> ans;
  getters[tmp] = ans;
  return getters[tmp];
}
long long gcd(long long x, long long y) { return y == 0 ? x : gcd(y, x % y); }
int mul(int a, int b) { return (int)((1LL * a * b) % mod); }
int bin_pow(int a, long long n) {
  long long r = 1;
  while (n > 0) {
    if (n & 1) {
      r = mul(r, a);
    }
    n >>= 1;
    a = mul(a, a);
  }
  return r;
}
long long reverse_element(long long a) { return bin_pow(a, mod - 2); }
long long get_x_in_pow(int x, int pow) { return bin_pow(x, pow); }
class sums_segment_tree {
 public:
  int n;
  vector<long long> val;
  vector<long long> pushes;
  vector<int> sizes;
  int l, r;
  long long ans, adding_value;
  void push(int v, bool is_leaf) {
    if (pushes[v] != 1) {
      val[v] *= bin_pow(pushes[v], sizes[v]);
      val[v] %= mod;
      if (!is_leaf) {
        int lp = v << 1;
        int rp = lp + 1;
        pushes[lp] *= pushes[v];
        pushes[rp] *= pushes[v];
        pushes[lp] %= mod;
        pushes[rp] %= mod;
      }
      pushes[v] = 1;
    }
  }
  void update(int v) {
    int lp = v << 1;
    int rp = lp + 1;
    long long left = val[lp];
    if (pushes[lp] != 1) {
      left *= bin_pow(pushes[lp], sizes[lp]);
      left %= mod;
    }
    long long right = val[rp];
    if (pushes[rp] != 1) {
      right *= bin_pow(pushes[rp], sizes[rp]);
      right %= mod;
    }
    val[v] = left * right;
    val[v] %= mod;
  }
  void build(vector<long long>& a, int v, int lb, int rb) {
    if (lb == rb) {
      val[v] = a[lb];
      sizes[v] = true;
      return;
    }
    int midt = (lb + rb) / 2;
    int lv = v << 1;
    int rv = lv + 1;
    build(a, lv, lb, midt);
    build(a, rv, midt + 1, rb);
    sizes[v] = sizes[lv] + sizes[rv];
    update(v);
  }
  void count(int v, int lb, int rb) {
    push(v, lb == rb);
    if (lb >= l && rb <= r) {
      ans *= val[v];
      ans %= mod;
    } else {
      int midt = (lb + rb) / 2;
      int lv = v << 1;
      int rv = lv + 1;
      if (midt >= l && lb <= r) count(lv, lb, midt);
      if (midt + 1 <= r && rb >= l) count(rv, midt + 1, rb);
    }
  }
  void add(int v, int lb, int rb) {
    push(v, lb == rb);
    if (lb >= l && rb <= r) {
      pushes[v] *= adding_value;
      if (pushes[v] >= mod) pushes[v] %= mod;
    } else {
      int midt = (lb + rb) / 2;
      int lv = v << 1;
      int rv = lv + 1;
      if (midt >= l && lb <= r) add(lv, lb, midt);
      if (midt + 1 <= r && rb >= l) add(rv, midt + 1, rb);
      update(v);
    }
  }

 public:
  sums_segment_tree(vector<long long>& a) {
    n = a.size();
    val.resize(n * 4, 1);
    pushes.resize(n * 4, 1);
    sizes.resize(n * 4, 0);
    build(a, 1, 0, n - 1);
  }
  long long get_answer(int l, int r) {
    this->l = l;
    this->r = r;
    this->ans = 1;
    count(1, 0, n - 1);
    return this->ans;
  }
  void add_on_segment(int l, int r, long long value) {
    this->l = l;
    this->r = r;
    this->adding_value = value;
    add(1, 0, n - 1);
  }
};
class segment_tree {
  int n;
  vector<long long> val;
  vector<long long> pushes;
  int l, r;
  long long ans, adding_value;
  void push(int v, bool is_leaf) {
    val[v] |= pushes[v];
    if (!is_leaf) {
      pushes[v << 1] |= pushes[v];
      pushes[(v << 1) + 1] |= pushes[v];
    }
    pushes[v] = 0;
  }
  void update(int v) {
    int lp = v << 1;
    int rp = lp + 1;
    val[v] = val[lp] | pushes[lp] | val[rp] | pushes[rp];
  }
  void build(vector<long long>& a, int v, int lb, int rb) {
    if (lb == rb) {
      val[v] = a[lb];
      return;
    }
    int midt = (lb + rb) / 2;
    int lv = v << 1;
    int rv = lv + 1;
    build(a, lv, lb, midt);
    build(a, rv, midt + 1, rb);
    update(v);
  }
  void count(int v, int lb, int rb) {
    push(v, lb == rb);
    if (lb >= l && rb <= r) {
      ans |= val[v];
    } else {
      int midt = (lb + rb) / 2;
      int lv = v << 1;
      int rv = lv + 1;
      if (midt >= l && lb <= r) count(lv, lb, midt);
      if (midt + 1 <= r && rb >= l) count(rv, midt + 1, rb);
    }
  }
  void add(int v, int lb, int rb) {
    push(v, lb == rb);
    if (lb >= l && rb <= r) {
      pushes[v] |= adding_value;
    } else {
      int midt = (lb + rb) / 2;
      int lv = v << 1;
      int rv = lv + 1;
      if (midt >= l && lb <= r) add(lv, lb, midt);
      if (midt + 1 <= r && rb >= l) add(rv, midt + 1, rb);
      update(v);
    }
  }

 public:
  segment_tree(vector<long long>& a) {
    n = a.size();
    val.resize(n * 4, 0);
    pushes.resize(n * 4, 0);
    build(a, 1, 0, n - 1);
  }
  long long get_answer(int l, int r) {
    this->l = l;
    this->r = r;
    this->ans = 0;
    count(1, 0, n - 1);
    return this->ans;
  }
  void add_on_segment(int l, int r, long long value) {
    this->l = l;
    this->r = r;
    this->adding_value = value;
    add(1, 0, n - 1);
  }
};
vector<int> primes;
vector<long long> reverse_elements;
vector<long long> dp;
void init_primes() {
  for (int i = 2; i < 305; i++) {
    bool f = true;
    for (auto j : primes) {
      if (i % j == 0) f = false;
    }
    if (f) primes.push_back(i);
  }
}
void init_reverses() {
  for (auto j : primes)
    reverse_elements.push_back((1 - reverse_element(j) + mod) % mod);
}
void init_dp() {
  init_primes();
  init_reverses();
  dp.resize(301, 0);
  for (int i = 1; i < 301; i++) {
    for (int j = 0; j < primes.size(); j++) {
      if (i % primes[j] == 0) dp[i] |= 1ll << j;
    }
  }
}
class query {
 public:
  int type, l, r, x;
  query() {
    string s;
    cin >> s >> l >> r;
    l--, r--;
    if (s[0] == 'T') {
      type = 0;
    } else {
      type = 1;
      cin >> x;
    }
  }
};
void solve() {
  cin >> n >> m;
  init_dp();
  vector<long long> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sums_segment_tree sums(a);
  vector<query> queries(m);
  vector<long long> tmp;
  for (int j = 0; j < n; j++) {
    tmp.push_back(dp[a[j]]);
  }
  segment_tree st(tmp);
  for (int q = 0; q < m; q++) {
    if (queries[q].type) {
      st.add_on_segment(queries[q].l, queries[q].r, dp[queries[q].x]);
      sums.add_on_segment(queries[q].l, queries[q].r, queries[q].x);
    } else {
      long long sums_ans = sums.get_answer(queries[q].l, queries[q].r);
      long long result = st.get_answer(queries[q].l, queries[q].r);
      for (int i = 0; i < primes.size(); i++) {
        if (result & (1ll << i)) {
          sums_ans *= reverse_elements[i];
          sums_ans %= mod;
        }
      }
      cout << sums_ans << "\n";
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  srand(58164);
  bool f = true;
  solve();
}

### Prompt

Generate a cpp solution to the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
int MAX_N = 30;
const int magic_const = 1e9 + 20;
const long long mod = 1e9 + 7;
const int LOG_NUM = 15;
class fenwick_tree {
  vector<long long> a;

 public:
  fenwick_tree(int n) { a.resize(n + 1); }
  void add(int pos, long long x) {
    for (pos++; pos < a.size(); pos += pos & -pos) {
      a[pos] += x;
    }
  }
  long long get(int pos) {
    long long answer = 0;
    for (pos++; pos > 0; pos -= pos & -pos) {
      answer += a[pos];
    }
    return answer;
  }
  long long get_sum(int left, int right) { return get(right) - get(left - 1); }
};
long long n, m;
int get_rand(int max_n) {
  return (int)(((rand() * (long long)RAND_MAX) + rand()) % max_n);
}
map<int, int> getters;
int tmp;
int get_ans(int tmp) {
  if (getters.find(tmp) != getters.end()) return getters[tmp];
  int ans;
  cout << "? " << tmp + 1 << endl;
  cin >> ans;
  getters[tmp] = ans;
  return getters[tmp];
}
long long gcd(long long x, long long y) { return y == 0 ? x : gcd(y, x % y); }
int mul(int a, int b) { return (int)((1LL * a * b) % mod); }
int bin_pow(int a, long long n) {
  long long r = 1;
  while (n > 0) {
    if (n & 1) {
      r = mul(r, a);
    }
    n >>= 1;
    a = mul(a, a);
  }
  return r;
}
long long reverse_element(long long a) { return bin_pow(a, mod - 2); }
long long get_x_in_pow(int x, int pow) { return bin_pow(x, pow); }
class sums_segment_tree {
 public:
  int n;
  vector<long long> val;
  vector<long long> pushes;
  vector<int> sizes;
  int l, r;
  long long ans, adding_value;
  void push(int v, bool is_leaf) {
    if (pushes[v] != 1) {
      val[v] *= bin_pow(pushes[v], sizes[v]);
      val[v] %= mod;
      if (!is_leaf) {
        int lp = v << 1;
        int rp = lp + 1;
        pushes[lp] *= pushes[v];
        pushes[rp] *= pushes[v];
        pushes[lp] %= mod;
        pushes[rp] %= mod;
      }
      pushes[v] = 1;
    }
  }
  void update(int v) {
    int lp = v << 1;
    int rp = lp + 1;
    long long left = val[lp];
    if (pushes[lp] != 1) {
      left *= bin_pow(pushes[lp], sizes[lp]);
      left %= mod;
    }
    long long right = val[rp];
    if (pushes[rp] != 1) {
      right *= bin_pow(pushes[rp], sizes[rp]);
      right %= mod;
    }
    val[v] = left * right;
    val[v] %= mod;
  }
  void build(vector<long long>& a, int v, int lb, int rb) {
    if (lb == rb) {
      val[v] = a[lb];
      sizes[v] = true;
      return;
    }
    int midt = (lb + rb) / 2;
    int lv = v << 1;
    int rv = lv + 1;
    build(a, lv, lb, midt);
    build(a, rv, midt + 1, rb);
    sizes[v] = sizes[lv] + sizes[rv];
    update(v);
  }
  void count(int v, int lb, int rb) {
    push(v, lb == rb);
    if (lb >= l && rb <= r) {
      ans *= val[v];
      ans %= mod;
    } else {
      int midt = (lb + rb) / 2;
      int lv = v << 1;
      int rv = lv + 1;
      if (midt >= l && lb <= r) count(lv, lb, midt);
      if (midt + 1 <= r && rb >= l) count(rv, midt + 1, rb);
    }
  }
  void add(int v, int lb, int rb) {
    push(v, lb == rb);
    if (lb >= l && rb <= r) {
      pushes[v] *= adding_value;
      if (pushes[v] >= mod) pushes[v] %= mod;
    } else {
      int midt = (lb + rb) / 2;
      int lv = v << 1;
      int rv = lv + 1;
      if (midt >= l && lb <= r) add(lv, lb, midt);
      if (midt + 1 <= r && rb >= l) add(rv, midt + 1, rb);
      update(v);
    }
  }

 public:
  sums_segment_tree(vector<long long>& a) {
    n = a.size();
    val.resize(n * 4, 1);
    pushes.resize(n * 4, 1);
    sizes.resize(n * 4, 0);
    build(a, 1, 0, n - 1);
  }
  long long get_answer(int l, int r) {
    this->l = l;
    this->r = r;
    this->ans = 1;
    count(1, 0, n - 1);
    return this->ans;
  }
  void add_on_segment(int l, int r, long long value) {
    this->l = l;
    this->r = r;
    this->adding_value = value;
    add(1, 0, n - 1);
  }
};
class segment_tree {
  int n;
  vector<long long> val;
  vector<long long> pushes;
  int l, r;
  long long ans, adding_value;
  void push(int v, bool is_leaf) {
    val[v] |= pushes[v];
    if (!is_leaf) {
      pushes[v << 1] |= pushes[v];
      pushes[(v << 1) + 1] |= pushes[v];
    }
    pushes[v] = 0;
  }
  void update(int v) {
    int lp = v << 1;
    int rp = lp + 1;
    val[v] = val[lp] | pushes[lp] | val[rp] | pushes[rp];
  }
  void build(vector<long long>& a, int v, int lb, int rb) {
    if (lb == rb) {
      val[v] = a[lb];
      return;
    }
    int midt = (lb + rb) / 2;
    int lv = v << 1;
    int rv = lv + 1;
    build(a, lv, lb, midt);
    build(a, rv, midt + 1, rb);
    update(v);
  }
  void count(int v, int lb, int rb) {
    push(v, lb == rb);
    if (lb >= l && rb <= r) {
      ans |= val[v];
    } else {
      int midt = (lb + rb) / 2;
      int lv = v << 1;
      int rv = lv + 1;
      if (midt >= l && lb <= r) count(lv, lb, midt);
      if (midt + 1 <= r && rb >= l) count(rv, midt + 1, rb);
    }
  }
  void add(int v, int lb, int rb) {
    push(v, lb == rb);
    if (lb >= l && rb <= r) {
      pushes[v] |= adding_value;
    } else {
      int midt = (lb + rb) / 2;
      int lv = v << 1;
      int rv = lv + 1;
      if (midt >= l && lb <= r) add(lv, lb, midt);
      if (midt + 1 <= r && rb >= l) add(rv, midt + 1, rb);
      update(v);
    }
  }

 public:
  segment_tree(vector<long long>& a) {
    n = a.size();
    val.resize(n * 4, 0);
    pushes.resize(n * 4, 0);
    build(a, 1, 0, n - 1);
  }
  long long get_answer(int l, int r) {
    this->l = l;
    this->r = r;
    this->ans = 0;
    count(1, 0, n - 1);
    return this->ans;
  }
  void add_on_segment(int l, int r, long long value) {
    this->l = l;
    this->r = r;
    this->adding_value = value;
    add(1, 0, n - 1);
  }
};
vector<int> primes;
vector<long long> reverse_elements;
vector<long long> dp;
void init_primes() {
  for (int i = 2; i < 305; i++) {
    bool f = true;
    for (auto j : primes) {
      if (i % j == 0) f = false;
    }
    if (f) primes.push_back(i);
  }
}
void init_reverses() {
  for (auto j : primes)
    reverse_elements.push_back((1 - reverse_element(j) + mod) % mod);
}
void init_dp() {
  init_primes();
  init_reverses();
  dp.resize(301, 0);
  for (int i = 1; i < 301; i++) {
    for (int j = 0; j < primes.size(); j++) {
      if (i % primes[j] == 0) dp[i] |= 1ll << j;
    }
  }
}
class query {
 public:
  int type, l, r, x;
  query() {
    string s;
    cin >> s >> l >> r;
    l--, r--;
    if (s[0] == 'T') {
      type = 0;
    } else {
      type = 1;
      cin >> x;
    }
  }
};
void solve() {
  cin >> n >> m;
  init_dp();
  vector<long long> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sums_segment_tree sums(a);
  vector<query> queries(m);
  vector<long long> tmp;
  for (int j = 0; j < n; j++) {
    tmp.push_back(dp[a[j]]);
  }
  segment_tree st(tmp);
  for (int q = 0; q < m; q++) {
    if (queries[q].type) {
      st.add_on_segment(queries[q].l, queries[q].r, dp[queries[q].x]);
      sums.add_on_segment(queries[q].l, queries[q].r, queries[q].x);
    } else {
      long long sums_ans = sums.get_answer(queries[q].l, queries[q].r);
      long long result = st.get_answer(queries[q].l, queries[q].r);
      for (int i = 0; i < primes.size(); i++) {
        if (result & (1ll << i)) {
          sums_ans *= reverse_elements[i];
          sums_ans %= mod;
        }
      }
      cout << sums_ans << "\n";
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  srand(58164);
  bool f = true;
  solve();
}

```