记 $g(i)$为 $i$在二进制下$1$ 的个数的奇偶性。 可以把$g(i)$ 视作二进制下每一位异或起来。所以$f(x,y)=g(x)⊕g(y)$ 。 所以考虑区间$[l,r]$ 建的图的时候可以令$a_i←g(a_i)$ ，变成 01 序列，这样只有权值不同的可以连边。所以是一张完全二分图。我们用某种方式数出 0和 1的个数$c$ 和$d$ ，则边数为 $cd$，$k>2$ 时，如果是奇数显然没有环，否则答案 是$\frac{1}{2} \binom{c}{\frac{k}{2}} \binom{d}{\frac{k}{2}} (\frac{k}{2})!(\frac{k}{2} -1)!$ 。预处理阶乘和组合数即可。 数据结构部分是区间翻转，区间求和。使用懒标记线段树即可。时间复杂度 $O(n+qlogn)$。 分块也能过。

/*
 *                                                     __----~~~~~~~~~~~------___
 *                                    .  .   ~~//====......          __--~ ~~
 *                    -.            \_|//     |||\\  ~~~~~~::::... /~
 *                 ___-==_       _-~o~  \/    |||  \\            _/~~-
 *         __---~~~.==~||\=_    -_--~/_-~|-   |\\   \\        _/~
 *     _-~~     .=~    |  \\-_    '-~7  /-   /  ||    \      /
 *   .~       .~       |   \\ -_    /  /-   /   ||      \   /
 *  /  ____  /         |     \\ ~-_/  /|- _/   .||       \ /
 *  |~~    ~~|--~~~~--_ \     ~==-/   | \~--===~~        .\
 *           '         ~-|      /|    |-~\~~       __--~~
 *                       |-~~-_/ |    |   ~\_   _-~            /\
 *                            /  \     \__   \/~                \__
 *                        _--~ _/ | .-~~____--~-/                  ~~==.
 *                       ((->/~   '.|||' -_|    ~~-/ ,              . _||
 *                                  -_     ~\      ~~---l__i__i__i--~~_/
 *                                  _-~-__   ~)  \--______________--~~
 *                                //.-~~~-~_--~- |-------~~~~~~~~
 *                                       //.-~~~--\
 *                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 *
 *                               神兽保佑            永无 BUG
 */

/*
 * @Description: I want to be the weakest vegetable in the world!
 * @Author: I.Z.
*/
#include<bits/stdc++.h>
using namespace std;
#define MOD         993244853
#define int         long long
#define pii         pair<int,int>
#define all(v)      v.begin(),v.end()
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
#define over(x)     {cout<<(x)<<endl;return;}
#define lowbit(x)   ((x)&(-(x)))
#define cntbit(x)   __builtin_popcount(x)
#define deal(v)     sort(all(v));v.erase(unique(v.begin(),v.end()),v.end())
#define lbound(v,x) lower_bound(all(v),x)-v.begin()
mt19937 sd(random_device{}());
int qpow(int a,int b,int m=MOD,int res=1){
	a%=m;
	while(b>0)res=(b&1)?(res*a%m):(res),a=a*a%m,b>>=1;
	return res;
}
int exgcd(int x,int y,int &a,int &b){
	if(y==0){
		a=1;b=0;
		return x;
	}
	int d=exgcd(y,x%y,a,b);
	int z=b;
	b=a-b*(x/y);
	a=z;
	return d;
}
int _x_,_y_;
inline int inverse(int x,int y=MOD){
	exgcd(x,y,_x_,_y_);
	return (_x_+y)%y;
}
int fac[2000005],inv[2000005];
void init(int n){
	fac[0]=inv[0]=1;
	REP(i,1,n+1)fac[i]=fac[i-1]*i%MOD;
	inv[n]=qpow(fac[n],MOD-2);
	for(int i=n-1;i>=1;--i)inv[i]=inv[i+1]*(i+1)%MOD;
}
int binom(int x,int y){
	return x<y||y<0? 0:fac[x]*inv[y]%MOD*inv[x-y]%MOD;
}
#define w(x) __builtin_parityll(x)
int n,q;
int a[200005];
int B;
int c1[20005],c2[20005],tag[20005];
void rebuild(int id){
	int l=id*B,r=min(n,(id+1)*B)-1;
	c1[id]=c2[id]=0;
	REP(i,l,r+1){
		a[i]^=tag[id];
		++(a[i]?c1[id]:c2[id]);
	}
	tag[id]=0;
}
void rev(int l,int r){
	if(l/B==r/B){
		REP(i,l,r+1)a[i]^=1;
		rebuild(l/B);
		return;
	}
	int li=l/B,ri=r/B;
	REP(i,l,(li+1)*B)a[i]^=1;
	rebuild(li);
	REP(i,ri*B,r+1)a[i]^=1;
	rebuild(ri);
	REP(i,li+1,ri){
		tag[i]^=1;
		swap(c1[i],c2[i]);
	}
}
int ask(int l,int r){
	int ans=0;
	if(l/B==r/B){
		REP(i,l,r+1)ans+=a[i]^tag[i/B];
	}else{
		int li=l/B,ri=r/B;
		REP(i,l,(li+1)*B)ans+=a[i]^tag[li];
		REP(i,ri*B,r+1)ans+=a[i]^tag[ri];
		REP(i,li+1,ri)ans+=c1[i];
	}
	return ans;
}
int cy[200005];
void Main(){
	cin>>n>>q;
	REP(i,0,n){
		cin>>a[i];
		a[i]=w(a[i]);
	}
	init(n);
	cy[2]=1;cy[4]=1; 
	for(int i=6;i<=n;i+=2){
		cy[i]=cy[i-2]*(i/2)%MOD*(i/2-1)%MOD;
	}
	B=sqrt(n);
	REP(i,0,(n-1)/B+1)rebuild(i);
	while(q--){
		int op,l,r,x;
		cin>>op>>l>>r>>x;
		--l,--r;
		if(op==1){
			x=w(x);
			if(x)rev(l,r);
		}else{
			if(x&1)cout<<0<<'\n';
			else{
				int p=ask(l,r);
				cout<<binom(p,x/2)*binom(r-l+1-p,x/2)%MOD*cy[x]%MOD<<'\n';
			}
		}
	}
}
void TC() {
    int tc=1;
	while(tc--){
		Main();
		cout.flush();
	}
}
signed main() {
	//freopen("still.in","r",stdin);
	//freopen("still.out","w",stdout);
	return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
}
/*
1. CLEAR the arrays (ESPECIALLY multitests)
2. DELETE useless output
 */