#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e5 + 5;
const int mod = 19940417;

int n, q;
int a[N], C[N][25];

struct Segment_Tree{
	int l, r;
	int add, mul;
	int f[25];
	
	void init(){
		l = r = 0;
		add = 0, mul = 1;
		f[0] = 1;
		for(int i = 1; i <= 20; i++){
			f[i] = 0;
		}
	}
}tree[N * 4];

inline void pushup(int node){
	for(int i = 1; i <= min(tree[node].r - tree[node].l + 1, (int)20); ++i){
		tree[node].f[i] = 0;
		for(int k = 0; k <= i; ++k){
			tree[node].f[i] = (tree[node].f[i] + (tree[node << 1].f[k] * tree[node << 1 | 1].f[i - k] % mod)) % mod;
		}
	}
}

inline void addtag1(int node, int val){
	val = (val % mod + mod) % mod;
	for(int i = min(tree[node].r - tree[node].l + 1, (int)20); i >= 1; --i){
		for(int k = 1, x = val; k <= i; ++k, x = x * val % mod){
			tree[node].f[i] = (tree[node].f[i] + ((C[tree[node].r - tree[node].l + 1 - i + k][k] * tree[node].f[i - k] % mod) * x % mod)) % mod;
		}
	}
	tree[node].add = (tree[node].add + val) % mod;
}

inline void addtag2(int node){
	for(int i = 1; i <= min(tree[node].r - tree[node].l + 1, (int)20); i += 2){
		tree[node].f[i] = ((mod - tree[node].f[i]) % mod + mod) % mod;
	}
	tree[node].add = ((mod - tree[node].add) % mod + mod) % mod;
	tree[node].mul %= -1;
}

inline void pushdown(int node){
	if(tree[node].mul != 1){
		addtag2(node << 1);
		addtag2(node << 1 | 1);
		tree[node].mul = 1;
	}
	if(tree[node].add){
		addtag1(node << 1, tree[node].add);
		addtag1(node << 1 | 1, tree[node].add);
		tree[node].add = 0;
	}
}

void build(int node, int lt, int rt){
	tree[node].init();
	tree[node].mul = 1;
	tree[node].add = 0;
	tree[node].l = lt;
	tree[node].r = rt;
	tree[node].f[0] = 1;
	if(lt == rt){
		tree[node].f[1] = a[lt];
		return ;
	}
	int mid = lt + rt >> 1;
	build(node << 1, lt, mid);
	build(node << 1 | 1, mid + 1, rt);
	pushup(node);
}

void update1(int node, int x, int y, int val){
	int lt = tree[node].l, rt = tree[node].r;
	if(x > rt || y < lt){
		return ;
	}
	if(x <= lt && rt <= y){
		addtag1(node, val);
		return ;
	}
	pushdown(node);
	update1(node << 1, x, y, val);
	update1(node << 1 | 1, x, y, val);
	pushup(node);
}

void update2(int node, int x, int y){
	int lt = tree[node].l, rt = tree[node].r;
	if(x > rt || y < lt){
		return ;
	}
	if(x <= lt && rt <= y){
		addtag2(node);
		return ;
	}
	pushdown(node);
	update2(node << 1, x, y);
	update2(node << 1 | 1, x, y);
	pushup(node);
}

Segment_Tree query(int node, int x, int y){
	int lt = tree[node].l, rt = tree[node].r;
	Segment_Tree ans;
	ans.init();
	if(x <= lt && rt <= y){
		return tree[node];
	}
	pushdown(node);
	int mid = lt + rt >> 1;
	if(y <= mid){
		return query(node << 1, x, y);
	}
	if(x > mid){
		return query(node << 1 | 1, x, y);
	}
	Segment_Tree tmp1, tmp2;
	tmp1.init(), tmp2.init();
	tmp1 = query(node << 1, x, mid), tmp2 = query(node << 1 | 1, mid + 1, y);
	for(int i = 1; i <= min(rt - lt + 1, (int)20); ++i){
		ans.f[i] = 0;
		for(int k = 0; k <= i; ++k){
			ans.f[i] = (ans.f[i] + (tmp1.f[k] * tmp2.f[i - k] % mod)) % mod;
		}
	}
	return ans;
}

signed main(){
	cin >> n >> q;
	for(int i = 0; i <= n; i++){
		C[i][0] = 1;
		for(int j = 1; j <= (i <= 20 ? i : 20); j++){
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
		}
	}
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		a[i] = (a[i] % mod + mod) % mod;
	}
	build(1, 1, n);
	while(q--){
		char op;
		cin >> op;
		if(op == 'I'){
			int l, r, c;
			cin >> l >> r >> c;
			update1(1, l, r, c);
		}
		else if(op == 'R'){
			int l, r;
			cin >> l >> r;
			update2(1, l, r);
		}
		else{
			int l, r, c;
			cin >> l >> r >> c;
			cout << query(1, l, r).f[c] << '\n';
		}
	}
	return 0;
}