#include <bits/stdc++.h>
inline long long mi(long long a, long long b, long long mo) {
  long long ans = 1ll;
  a %= mo;
  while (b) {
    if (b & 1) ans = ans * a % mo;
    b >>= 1;
    a = a * a % mo;
  }
  return ans;
}
inline long long read() {
  long long t = 0;
  bool neg = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') neg = 1;
    ch = getchar();
  }
  do {
    t = t * 10 + ch - '0';
    ch = getchar();
  } while (ch >= '0' && ch <= '9');
  if (neg) t = -t;
  return t;
}
long long readOpt() {
  char ch = getchar();
  long long ans;
  while (ch < 'A' || ch > 'Z') ch = getchar();
  if (ch == 'T')
    return 2;
  else
    return 1;
}
struct Node {
  long long val;
  long long p;
  long long lazy, lazyP;
  Node() {
    val = 1;
    lazy = 1;
    p = 0;
    lazyP = 0;
  }
} xds[1600007];
long long n, q;
long long a[1600007];
long long f[1001], inv[1001];
long long prime[] = {2,   3,   5,   7,   11,  13,  17,  19,  23,  29,  31,
                     37,  41,  43,  47,  53,  59,  61,  67,  71,  73,  79,
                     83,  89,  97,  101, 103, 107, 109, 113, 127, 131, 137,
                     139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,
                     197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257,
                     263, 269, 271, 277, 281, 283, 293};
void pushUp(long long x) {
  xds[x].val = xds[x * 2].val * xds[x * 2 + 1].val % 1000000007;
  xds[x].p = xds[x * 2].p | xds[x * 2 + 1].p;
}
void pushDown(long long x, long long l, long long m, long long r) {
  xds[x * 2].val =
      xds[x * 2].val * mi(xds[x].lazy, m - l + 1, 1000000007) % 1000000007;
  xds[x * 2 + 1].val =
      xds[x * 2 + 1].val * mi(xds[x].lazy, r - m, 1000000007) % 1000000007;
  xds[x * 2].lazy = xds[x * 2].lazy * xds[x].lazy % 1000000007;
  xds[x * 2 + 1].lazy = xds[x * 2 + 1].lazy * xds[x].lazy % 1000000007;
  xds[x * 2].p |= xds[x].lazyP;
  xds[x * 2 + 1].p |= xds[x].lazyP;
  xds[x * 2].lazyP |= xds[x].lazyP;
  xds[x * 2 + 1].lazyP |= xds[x].lazyP;
  xds[x].lazy = 1;
  xds[x].lazyP = 0;
}
void build(long long l, long long r, long long x) {
  if (l == r) {
    xds[x].val = a[l];
    for (long long i = 0; i < 62; ++i)
      if (a[l] % prime[i] == 0) xds[x].p |= (1ll) << i;
    return;
  }
  const long long m = (l + r) >> 1;
  build(l, m, x * 2);
  build(m + 1, r, x * 2 + 1);
  pushUp(x);
}
void update(long long x, long long l, long long r, long long delta,
            long long prime, long long cl, long long cr) {
  if (cl > r || cr < l) return;
  if (l <= cl && cr <= r) {
    xds[x].val = xds[x].val * mi(delta, cr - cl + 1, 1000000007) % 1000000007;
    xds[x].lazy = xds[x].lazy * delta % 1000000007;
    xds[x].p |= prime;
    xds[x].lazyP |= prime;
    return;
  }
  const long long m = (cl + cr) >> 1;
  pushDown(x, cl, m, cr);
  update(x * 2, l, r, delta, prime, cl, m);
  update(x * 2 + 1, l, r, delta, prime, m + 1, cr);
  pushUp(x);
}
Node query(long long x, long long l, long long r, long long cl, long long cr) {
  if (cl > r || cr < l) return Node();
  if (l <= cl && r >= cr) {
    return xds[x];
  }
  const long long m = (cl + cr) >> 1;
  pushDown(x, cl, m, cr);
  Node n;
  Node ll = query(x * 2, l, r, cl, m);
  Node rr = query(x * 2 + 1, l, r, m + 1, cr);
  n.val = ll.val * rr.val % 1000000007;
  n.p = ll.p | rr.p;
  return n;
}
signed main() {
  n = read(), q = read();
  for (long long i = 1; i <= n; ++i) a[i] = read();
  build(1, n, 1);
  inv[1] = 1;
  for (long long i = 2; i <= 300; ++i)
    inv[i] = 1000000007 - (1000000007 / i) * inv[1000000007 % i] % 1000000007;
  for (long long i = 0; i < 62; ++i)
    f[i] = inv[prime[i]] * (prime[i] - 1) % 1000000007;
  for (long long i = 1; i <= q; i += 1) {
    long long opt = readOpt(), x = read(), y = read();
    if (opt == 1) {
      long long k = read();
      long long t = 0;
      for (long long i = 0; i < 62; ++i)
        if (k % prime[i] == 0) t |= (1ll) << i;
      update(1, x, y, k, t, 1, n);
    } else {
      Node ans = query(1, x, y, 1, n);
      long long phi = ans.val;
      for (long long i = 0; i < 62; ++i) {
        if (ans.p >> i & 1) {
          phi = phi * f[i] % 1000000007;
        }
      }
      printf("%lld\n", phi % 1000000007);
    }
  }
  return 0;
}

### 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>
inline long long mi(long long a, long long b, long long mo) {
  long long ans = 1ll;
  a %= mo;
  while (b) {
    if (b & 1) ans = ans * a % mo;
    b >>= 1;
    a = a * a % mo;
  }
  return ans;
}
inline long long read() {
  long long t = 0;
  bool neg = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') neg = 1;
    ch = getchar();
  }
  do {
    t = t * 10 + ch - '0';
    ch = getchar();
  } while (ch >= '0' && ch <= '9');
  if (neg) t = -t;
  return t;
}
long long readOpt() {
  char ch = getchar();
  long long ans;
  while (ch < 'A' || ch > 'Z') ch = getchar();
  if (ch == 'T')
    return 2;
  else
    return 1;
}
struct Node {
  long long val;
  long long p;
  long long lazy, lazyP;
  Node() {
    val = 1;
    lazy = 1;
    p = 0;
    lazyP = 0;
  }
} xds[1600007];
long long n, q;
long long a[1600007];
long long f[1001], inv[1001];
long long prime[] = {2,   3,   5,   7,   11,  13,  17,  19,  23,  29,  31,
                     37,  41,  43,  47,  53,  59,  61,  67,  71,  73,  79,
                     83,  89,  97,  101, 103, 107, 109, 113, 127, 131, 137,
                     139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,
                     197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257,
                     263, 269, 271, 277, 281, 283, 293};
void pushUp(long long x) {
  xds[x].val = xds[x * 2].val * xds[x * 2 + 1].val % 1000000007;
  xds[x].p = xds[x * 2].p | xds[x * 2 + 1].p;
}
void pushDown(long long x, long long l, long long m, long long r) {
  xds[x * 2].val =
      xds[x * 2].val * mi(xds[x].lazy, m - l + 1, 1000000007) % 1000000007;
  xds[x * 2 + 1].val =
      xds[x * 2 + 1].val * mi(xds[x].lazy, r - m, 1000000007) % 1000000007;
  xds[x * 2].lazy = xds[x * 2].lazy * xds[x].lazy % 1000000007;
  xds[x * 2 + 1].lazy = xds[x * 2 + 1].lazy * xds[x].lazy % 1000000007;
  xds[x * 2].p |= xds[x].lazyP;
  xds[x * 2 + 1].p |= xds[x].lazyP;
  xds[x * 2].lazyP |= xds[x].lazyP;
  xds[x * 2 + 1].lazyP |= xds[x].lazyP;
  xds[x].lazy = 1;
  xds[x].lazyP = 0;
}
void build(long long l, long long r, long long x) {
  if (l == r) {
    xds[x].val = a[l];
    for (long long i = 0; i < 62; ++i)
      if (a[l] % prime[i] == 0) xds[x].p |= (1ll) << i;
    return;
  }
  const long long m = (l + r) >> 1;
  build(l, m, x * 2);
  build(m + 1, r, x * 2 + 1);
  pushUp(x);
}
void update(long long x, long long l, long long r, long long delta,
            long long prime, long long cl, long long cr) {
  if (cl > r || cr < l) return;
  if (l <= cl && cr <= r) {
    xds[x].val = xds[x].val * mi(delta, cr - cl + 1, 1000000007) % 1000000007;
    xds[x].lazy = xds[x].lazy * delta % 1000000007;
    xds[x].p |= prime;
    xds[x].lazyP |= prime;
    return;
  }
  const long long m = (cl + cr) >> 1;
  pushDown(x, cl, m, cr);
  update(x * 2, l, r, delta, prime, cl, m);
  update(x * 2 + 1, l, r, delta, prime, m + 1, cr);
  pushUp(x);
}
Node query(long long x, long long l, long long r, long long cl, long long cr) {
  if (cl > r || cr < l) return Node();
  if (l <= cl && r >= cr) {
    return xds[x];
  }
  const long long m = (cl + cr) >> 1;
  pushDown(x, cl, m, cr);
  Node n;
  Node ll = query(x * 2, l, r, cl, m);
  Node rr = query(x * 2 + 1, l, r, m + 1, cr);
  n.val = ll.val * rr.val % 1000000007;
  n.p = ll.p | rr.p;
  return n;
}
signed main() {
  n = read(), q = read();
  for (long long i = 1; i <= n; ++i) a[i] = read();
  build(1, n, 1);
  inv[1] = 1;
  for (long long i = 2; i <= 300; ++i)
    inv[i] = 1000000007 - (1000000007 / i) * inv[1000000007 % i] % 1000000007;
  for (long long i = 0; i < 62; ++i)
    f[i] = inv[prime[i]] * (prime[i] - 1) % 1000000007;
  for (long long i = 1; i <= q; i += 1) {
    long long opt = readOpt(), x = read(), y = read();
    if (opt == 1) {
      long long k = read();
      long long t = 0;
      for (long long i = 0; i < 62; ++i)
        if (k % prime[i] == 0) t |= (1ll) << i;
      update(1, x, y, k, t, 1, n);
    } else {
      Node ans = query(1, x, y, 1, n);
      long long phi = ans.val;
      for (long long i = 0; i < 62; ++i) {
        if (ans.p >> i & 1) {
          phi = phi * f[i] % 1000000007;
        }
      }
      printf("%lld\n", phi % 1000000007);
    }
  }
  return 0;
}

```