#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ull unsigned long long

using namespace std;

const int N = 4e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

const double PI = acos(-);

int n, q, tot, b[N], prime[], mul[];

LL S[];

char op[];

bool ok(int x) {

    for(int i = ; i * i <= x; i++)

        if(x % i == ) return false;

    return true;

}

int Power(int a, int b) {

    int ans = ;

    while(b) {

        if(b & ) ans = 1ll * ans * a % mod;

        a = 1ll * a * a % mod; b >>= ;

    }

    return ans;

}

int a[N << ], lazy[N << ];

LL mask[N << ], mlazy[N << ];

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

inline void pull(int rt) {

    a[rt] = 1ll * a[rt << ] * a[rt <<  | ] % mod;

    mask[rt] = mask[rt << ] | mask[rt <<  | ];

}

void push(int rt, int l, int mid, int r) {

    if(lazy[rt] != ) {

        a[rt << ] = 1ll * a[rt << ] * Power(lazy[rt], mid - l + ) % mod;

        a[rt <<  | ] = 1ll * a[rt <<  | ] * Power(lazy[rt], r - mid) % mod;

        lazy[rt << ] = 1ll * lazy[rt << ] * lazy[rt] % mod;

        lazy[rt <<  | ] = 1ll * lazy[rt <<  | ] * lazy[rt] % mod;

        lazy[rt] = ;

    }

    if(mlazy[rt] != ) {

        mask[rt << ] |= mlazy[rt]; mask[rt <<  | ] |= mlazy[rt];

        mlazy[rt << ] |= mlazy[rt]; mlazy[rt <<  | ] |= mlazy[rt];

        mlazy[rt] = ;

    }

}

void build(int l, int r, int rt) {

    lazy[rt] = ;

    mlazy[rt] = ;

    if(l == r) {

        a[rt] = b[l];

        mask[rt] = S[b[l]];

        return;

    }

    int mid = l + r >> ;

    build(lson); build(rson);

    pull(rt);

}

void update(int L, int R, int mul, int l, int r, int rt) {

    if(l >= L && r <= R) {

        a[rt] = 1ll * a[rt] * Power(mul, r - l + ) % mod;

        lazy[rt] = 1ll * lazy[rt] * mul % mod;

        mask[rt] |= S[mul];

        mlazy[rt] |= S[mul];

        return;

    }

    int mid = l + r >> ;

    push(rt, l, mid, r);

    if(L <= mid) update(L, R, mul, lson);

    if(R > mid) update(L, R, mul, rson);

    pull(rt);

}

PLI query(int L, int R, int l, int r, int rt) {

    if(l >= L && r <= R) return mk(mask[rt], a[rt]);

    int mid = l + r >> ;

    push(rt, l, mid, r);

    PLI ans = mk(, );

    if(L <= mid) {

        PLI tmp = query(L, R, lson);

        ans.fi |= tmp.fi;

        ans.se = 1ll * ans.se * tmp.se % mod;

    }

    if(R > mid) {

        PLI tmp = query(L, R, rson);

        ans.fi |= tmp.fi;

        ans.se = 1ll * ans.se * tmp.se % mod;

    }

    return ans;

}

int main() {

    for(int i = ; i <= ; i++)

        if(ok(i)) prime[tot++] = i;

    for(int i = ; i < tot; i++)

        mul[i] = ( - Power(prime[i], mod - ) + mod) % mod;

    for(int i = ; i <= ; i++)

        for(int j = ; j < tot && prime[j] <= i; j++)

            if(i % prime[j] == ) S[i] |= 1ll << j;

    scanf("%d%d", &n, &q);

    for(int i = ; i <= n; i++) scanf("%d", &b[i]);

    build(, n, );

    while(q--) {

        scanf("%s", op);

        if(op[] == 'T') {

            int L, R; scanf("%d%d", &L, &R);

            PLI ret = query(L, R, , n, );

            int ans = ret.se; LL mask = ret.fi;

            for(int i = ; i < tot; i++)

                if(mask >> i & ) ans = 1ll * ans * mul[i] % mod;

            printf("%d\n", ans);

        } else {

            int L, R, x;

            scanf("%d%d%d", &L, &R, &x);

            update(L, R, x, , n, );

        }

    }

    return ;

}

/*

*/