## 描述

You are given an array $a_1, a_2, \ldots, a_n$.

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

1. "MULTIPLY l r x" — for every $i$ ($l \le i \le r$) multiply $a_i$ by $x$.
2. "TOTIENT l r" — print$\varphi(\prod \limits_{i=l}^{r} a_i)$ taken modulo $10^9+7$, where $\varphi$ denotes Euler's totient function.
The Euler's totient function of a positive integer $n$ (denoted as $\varphi(n)$) is the number of integers $x$ ($1 \le x \le n$) such that $\gcd(n,x) = 1$

### Input

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

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 300$) — the elements of array $a$.

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

"MULTIPLY l r x" ($1 \le l \le r \le n$, $1 \le x \le 300$) — denotes a multiplication query.
"TOTIENT l r" ($1 \le l \le r \le 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.

## 思路

• 首先我们知道：若 $n = \prod\limits_{i = 1} ^ r p_i^{k_i}$，则 $\varphi(n) = \prod\limits_{i = 1} ^ r p_i ^ {k_i - 1} (p_i - 1) = n \prod\limits_{p | n}(1 - \frac{1}{p})$。其中 $p$ 是质数。
• 方法一：根据最后的式子，我们只需要维护两个量：区间的乘积、区间的质因子。这可以分别使用两个线段树来维护和合并信息。由于 $300$ 内一共有 $62$ 个质数（打表可知），所以可以使用 long long 来压状态。然后就是正常的线段树打标记没什么好说的了。
• 方法二：根据前面一个式子，我们可以分别维护每个质因子的个数来计算其对答案的贡献。这样需要开 $62$ 个线段树，妥妥MLE。 由于每个质因子是独立的，所以我们可以考虑将所有操作离线，分别处理每个质因子，这样就只需要开一个了。但是由于种种原因（似乎是线段树的常数太大），我是用两个树状数组完成区间加和查询区间和的。

## 代码

### 方法一

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const static int N = 1 << 19;
const static int mod = 1e9 + 7;
vector<int> p, invp;
ll Pow(ll a, ll n)
{
ll t = 1;
for (; n; n >>= 1, (a *= a) %= mod)
if (n & 1) (t *= a) %= mod;
return t;
}
inline bool isprime(int n)
{
for (int i = 2; i * i <= n; i++)
if (n % i == 0) return false;
return n != 1;
}
void init(int n)
{
for (int i = 2; i <= n; i++)
if (isprime(i)) p.push_back(i);
for (auto t : p)
invp.push_back(Pow(t, mod - 2));
}
ll gao(int x)
{
ll ret = 0;
for (int i = 0; i < p.size(); i++)
if (x % p[i] == 0) ret |= (1LL << i);
return ret;
}
namespace Segment_Tree
{
typedef long long type_t;
type_t pro[N << 2], bit[N << 2];
type_t mul[N << 2], tag[N << 2];
#define lson o << 1
#define rson o << 1 | 1
#define Lson l, m, lson
#define Rson m + 1, r, rson
inline void pushup(int o)
{
pro[o] = (pro[lson] * pro[rson]) % mod;
bit[o] = (bit[lson] | bit[rson]);
}
inline void pushdown(int o, int m)
{
if (mul[o] != 1)
{
(mul[lson] *= mul[o]) %= mod;
(mul[rson] *= mul[o]) %= mod;
(pro[lson] *= Pow(mul[o], m - (m >> 1))) %= mod;
(pro[rson] *= Pow(mul[o], m >> 1)) %= mod;
mul[o] = 1;
}
if (tag[o] != 0)
{
tag[lson] |= tag[o];
tag[rson] |= tag[o];
bit[lson] |= tag[o];
bit[rson] |= tag[o];
tag[o] = 0;
}
}
void build(int l = 1, int r = N, int o = 1)
{
mul[o] = 1, tag[o] = 0;
if (l == r)
{
scanf("%lld", &pro[o]);
bit[o] = gao(pro[o]);
return;
}
const int m = l + r >> 1;
build(Lson);
build(Rson);
pushup(o);
}
void update(int L, int R, pair<type_t, type_t> v, int l = 1, int r = N, int o = 1)
{
if (L <= l && r <= R)
{
(mul[o] *= v.first) %= mod;
(pro[o] *= Pow(v.first, r - l + 1)) %= mod;
tag[o] |= v.second;
bit[o] |= v.second;
return;
}
pushdown(o, r - l + 1);
const int m = l + r >> 1;
if (L <= m) update(L, R, v, Lson);
if (m < R) update(L, R, v, Rson);
pushup(o);
}
pair<type_t, type_t>& operator|=(pair<type_t, type_t>& a, const pair<type_t, type_t>& b)
{
(a.first *= b.first) %= mod;
a.second |= b.second;
}
pair<type_t, type_t> query(int L, int R, int l = 1, int r = N, int o = 1)
{
if (L <= l && r <= R) return make_pair(pro[o], bit[o]);
pushdown(o, r - l + 1);
const int m = l + r >> 1;
pair<type_t, type_t> ret = make_pair(1, 0);
if (L <= m) ret |= query(L, R, Lson);
if (m < R) ret |= query(L, R, Rson);
return ret;
}
#undef lson
#undef rson
#undef Lson
#undef Rson
}; // namespace Segment_Tree
int main()
{
init(300);
int n, q;
scanf("%d%d", &n, &q);
Segment_Tree::build(1, n, 1);
for (int i = 0, l, r, x; i < q; i++)
{
static char op[10];
scanf("%s%d%d", op, &l, &r);
long long prod, bit;
if (op[0] == 'T')
{
tie(prod, bit) = Segment_Tree::query(l, r, 1, n, 1);
for (int i = 0; i < p.size(); i++)
if (bit >> i & 1) prod = prod * (p[i] - 1) % mod * invp[i] % mod;
printf("%lld\n", prod);
}
else
{
scanf("%d", &x);
prod = x, bit = 0;
for (int i = 0; i < p.size(); i++)
if (x % p[i] == 0) bit |= 1LL << i;
Segment_Tree::update(l, r, make_pair(prod, bit), 1, n, 1);
}
}
}

### 方法二

#include <bits/stdc++.h>
using namespace std;

const int N = 4e5 + 5;
typedef long long ll;
ll num[N], sum[N];
const int mod = 1e9 + 7;
inline void update(int x, ll v, ll* bit)
{
for (; x < N; x += x & -x) bit[x] += v;
}
inline ll query(int x, ll* bit)
{
ll t = 0;
for (; x; x -= x & -x) t += bit[x];
return t;
}
vector<int> prime;
bool isprime(int n)
{
for (int i = 2; i * i <= n; i++)
if (n % i == 0) return false;
return n != 1;
}
void init(int n)
{
int tot = 0;
for (int i = 2; i <= n; i++)
if (isprime(i)) prime.push_back(i);
}
ll Pow(ll a, ll n)
{
ll t = 1;
for (; n; n >>= 1, (a *= a) %= mod)
if (n & 1) (t *= a) %= mod;
return t;
}
void update(int l, int r, ll x)
{
update(l, x, num);
update(r + 1, -x, num);
update(l, 1LL * (l - 1) * x, sum);
update(r + 1, 1LL * (-r) * x, sum);
}
ll query(int l, int r)
{
return (1LL * r * query(r, num) - query(r, sum))
- (1LL * (l - 1) * query(l - 1, num) - query(l - 1, sum));
}

int a[N];
int l[N], r[N], x[N];
ll ans[N];
int main()
{
init(300);
int n, q;
scanf("%d%d", &n, &q);
int M = prime.size();
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 0; i < q; i++)
{
static char op[10];
scanf("%s%d%d", op, &l[i], &r[i]);
if (op[0] == 'T')
x[i] = -1;
else
scanf("%d", &x[i]);
ans[i] = 1;
}
for (int t = 0; t < M; t++)
{
memset(num, 0, sizeof(num));
memset(sum, 0, sizeof(sum));
for (int i = 1; i <= n; i++)
{
int cnt = 0;
while (a[i] % prime[t] == 0)
{
cnt++;
a[i] /= prime[t];
}
if (cnt) update(i, i, cnt);
}
for (int i = 0; i < q; i++)
{
if (~x[i])
{
int cnt = 0;
while (x[i] % prime[t] == 0)
{
cnt++;
x[i] /= prime[t];
}
if (cnt) update(l[i], r[i], cnt);
}
else
{
ll cnt = query(l[i], r[i]);
if (cnt)
{
ans[i] = ans[i] * Pow(prime[t], cnt - 1) % mod;
ans[i] = ans[i] * (prime[t] - 1) % mod;
}
}
}
}
for (int i = 0; i < q; i++)
if (!~x[i]) printf("%lld\n", ans[i]);
}