最初に、\(A\) を非負整数列として問題を解くため、各条件の \(S_i\) を \(S_i-(R_i-L_i+1)\) と変更します。変更後の条件をみたす非負整数列 \(A\) は、それぞれの要素 \(A_i\) に \(1\) を加えることで、元の条件をみたす正整数列と一対一に対応し、特に答えは等しくなります。

以下では、\(2\) つのステップに分けて問題を解きます。

1. 与えられた条件に両立不能なものがないか確認し、必要十分条件を整理する。

\(A\) の累積和 \(B\) を、\(B_0=0, B_i=B_{i-1}+A_i\) \((1\leq i\leq N)\) と定義します。

与えられる条件は、\(B_{R_i}-B_{L_i-1}=S_i\) と書くことができます。
ここで、与えられた条件をもとに、\(B_i=B_{k_i}+D_i\) と記述することを考えます。ここで、\(k_i\) はこのように書けるような最小の添字です。
最初、すべての\(i\) について、\(k_i=i, D_i=0\) です。\(i=1,2,\ldots,M\) の順で条件に応じて次のいずれかの操作を行います。

• \(k_{L_i-1}=k_{R_i}\) のとき

このとき、それまでの条件から、\(B_{L_i-1}=B_{k_{L_i-1}}+D_{L_i-1}\), \(B_{R_i}=B_{k_{R_i}}+D_{R_i}\) であり、特に \(B_{R_i}=B_{L_i-1}+(D_{R_i}-D_{L_i-1})\) が成り立っています。
よって、\(S_i\neq D_{R_i}-D_{L_i-1}\) のとき、すべての条件をみたす \(A\) は存在しないため、答えは \(0\) となります。（実装上はこの場合ただちにプログラムを終了することができます。）そうでない場合は、それまでの条件からこの条件は自動的にみたされるため、何も行わず、次の \(i\) に移ります。

• \(k_{L_i-1}< k_{R_i}\) のとき

現在の条件は \(B_{k_{R_i}}+D_{R_i}=B_{L_i-1}=(B_{k_{L_i-1}}+D_{L_i-1})+S_i\) と書くことができ、これを整理すると \(B_{k_{R_i}}=B_{k_{L_i-1}}+(D_{L_i-1}+S_i-D_{R_i})\) となります。よって、\(B_{k_{R_i}}+\) （定数）の形で書くことのできる \(B_j\) は \(B_{k_{L_i-1}}+\)（定数）の形で書くことができるため、 \(k_j=k_{R_i}\) であるようなすべての \(j\) について、\(k_j \leftarrow k_{L_i-1}\), \(D_j \leftarrow D_j+(D_{L_i-1}+S_i-D_{R_i})\) と更新します。（ここで、\(\leftarrow\) は代入を意味します。）

• \(k_{L_i-1}> k_{R_i}\) のとき

\(k_{L_i-1}< k_{R_i}\) のときと同様の理由で、ただし、\(k_{L_i-1}> k_{R_i}\). であるため、\(k_j=k_{L_i-1}\) であるようなすべての \(j\) について、\(k_j \leftarrow k_{R_i}\), \(D_j \leftarrow D_j+(D_{R_i}-D_{L_i-1}-S_i)\) と更新します。

すべての \(i\) について操作を行った後で、\(j=0,1,\ldots,N-1\)について次のようにして条件を列挙します。

• \(j'>j\) かつ \(k_{j'}=k_j\) であるような \(j'\) が存在しないならば何もしない。存在するならばそのようなもののうち最小の \(j'\) について、\(A_{j+1}+A_{j+2}+\cdots+A_{j'}=B_{j'}-B_j=D_{j'}-D_j\) を条件として挙げる。ここで、右辺 \(D_{j'}-D_j\) が \(0\) 未満となったとき、やはり条件をみたす \(A\) は存在しないため \(0\) を出力する。

このようにして得られた条件の集合を入力で与えられた条件をすべてみたす必要十分条件となっています。これが必要条件であることは \(k_j,D_j\) の定義から明らかであり、また、入力として与えられた条件について、一連の操作の後で必ず \(k_{L_i-1}=k_{R_i}\) となっていることから、列挙された条件を適切に足し合わせることで元の式が得られ、すなわち列挙された条件がすべてみたされるときその条件も自動的にみたされることが従います。

また、定義より、この得られた条件式の左辺 \(A_{j+1}+A_{j+2}+\cdots+A_{j'}\) を含む部分和を左辺とする条件が入力の中に存在することから、上記で得られたすべての右辺が非負であるという条件下で、新しく得られた式の右辺もすべて \(10^9\) 以下となることが従います。

このステップの結論として、両立不能な条件が存在するなら上記の操作の中で発見され、そうでないとき、非負整数列 \(A=(A_1,\ldots, A_N)\) が入力の条件をみたす必要十分条件は上記で列挙された

• \(A_{L'_i}+\cdots+A_{R'_i}=S'_i\)

をすべてみたすこととなります。特に先に述べた列挙方法より、 \(L'_i\) はすべて異なるため、高々 \(N\) 個の式で表されています。以下、この条件式の数を \(M'\) とします。

また、この \(M'\) 個の式に一度も登場しない \(A_j\) \((1\leq j\leq N)\) が存在する場合、答えは \(0\) または Infinity になります。なお、これは元の \(M\) 個の式に一度も登場しない \(A_j\) が存在するかと同値であることに注意してください。この場合については後に述べるため、以下ではすべての \(A_j\) が一度以上ずつ登場しているものとします。このとき、先に述べたように右辺がすべて \(10^9\) 以下であることから、すべての \(A_j\) が \(10^9\) 以下である場合のみを考えれば十分であることが従います。

2. \(2\) 進数桁DPによって、答えを求める。

\(dp[i][(C_1,C_2,\ldots,C_{M'})]\) を \(A_1,\ldots,A_N\) をそれぞれ \(2\) 進数表記した時の \(i\) 桁目までの組み合わせであって、以下の条件をすべてみたすものとして定義します。

• \(j=1,2,\ldots,M'\) について、\(A_{L'_j}+\cdots+A_{R'_j}\equiv S'_j \pmod{2^i}\)
• \(j=1,2,\ldots,M'\) について、\(\{ (A_{L'_j} \% 2^i)+\cdots +(A_{R'_j} \% 2^i)-(S'_j\%2^i)\}/2^i=C_j\)

ここで、\(X\%Y\) で \(X\) を \(Y\) で割った余り（最小非負剰余）を表します。特に、\(A_j\%2^i\) は \(A_j\) を \(2\) 進数表記した時の下 \(i\) 桁を取り出したものとなります。 \(C_j\) は \(1\) つめの条件をみたす時必ず整数であり、 \(0\) 以上 \((R_j-L_j)\) 以下の値をとります。

先に述べたように条件式の両辺の各項が \(10^9\) 以下である場合のみを考えれば良いことから、下から \(31\) 桁目（\(2^{30}\) の位）以上の桁は両辺ですべて \(0\) であるとして良く、答えは \(dp[30][(0,0,\ldots,0)]\%998244353\) となります。 初期値は \(dp[0][(0,0,\ldots,0)]=1\) であり、\(C\neq (0,0,\ldots,0)\) について \(dp[0][C]=0\) です。

遷移について、 \(dp[i-1][C]\) からの遷移は各 \(A_j\) の \(i\) 桁目の組み合わせ\(X^i=(X^i_1,\ldots,X^i_N)\) \((X^i_j\in\{0,1\})\) のうち、\(i\) 桁目において条件の式をすべてみたすものになります。
すなわち、\(d(Z, i)\) で \(Z\) の \(i\) 桁目を表すとして、 \(2^N\) 通りの \(X^i\) のうち、すべての \(j\) について、

• \(C_j+X^i_{L'_j}+X^i_{L'_j+1}+\cdots+X^i_{R'_j}\equiv d(S'_j,i) \pmod{2}\)

をみたすものについて、

• \(C'_j=\frac{1}{2}\{C_j+X^i_{L'_j}+X^i_{L'_j+1}+\cdots+X^i_{R'_j}-d(S'_j,i) \}\)

として、\(dp[i][C']\leftarrow dp[i][C']+dp[i-1][C]\) と更新を行えば良いです。

このようにして答えを求めることが可能なことがわかりました。
計算量について、重要なのは繰り上がりの組み合わせ \(C\) として考えられるものがいくつあるかです。これは高々 \((R'_1-L'_1+1)\times (R'_2-L'_2+1)\times \cdots (R_{M'}-L_{M'}+1)\) 通りあります。これはステップ \(1\) のように \((L'_j,R'_j,S'_j)\) を決定したとき、問題の制約 \(N\leq 8\) 下において最大で \(1024\) 通りとなります。これは \(k_0,k_1,\ldots,k_N\) の中に何種類の値が存在するかで場合分けすることによって比較的簡単に求めることができます、

各\(C\) から遷移し得る \(C'\) の列挙（およびそれを達成する \(X^i\) の個数）は前計算することができます、このために必要な計算回数は上記の式をナイーブに計算しても、\(1024\times 2^8\times 8\times 8=2^{24}\) 回程度で可能です。また、実際の DP の遷移の計算回数も高々 \(30\times 1024\times 2^8\simeq 8\times 10^6\) であり、\(C\) と 添字を対応させるために unordered_map 等を使っても十分間に合います。 よって、この場合において、十分高速に問題を解くことができることがわかりました。

Infinity の判定について

最後に、ステップ \(1\) の最後に述べた、\(M'\) 個の式に一度も登場しない \(A_j\) \((1\leq j\leq N)\) が存在する場合の \(0\) または Infinity の判定について述べます。結論から言えば、これは \(dp[30][(0,0,\ldots,0)]=0\) ならば \(0\), そうでないならば Infinity となります。ここで注意しなければならないのは、\(dp[30][(0,0,\ldots,0)]\equiv 0 \pmod{998244353}\) であっても、\(dp[30][(0,0,\ldots,0)]>0\) ならば Infinity となることです。

\(dp[30][(0,0,\ldots,0)]=0\), すなわち \((A_1,\ldots,A_N)\) のうちの（条件に登場する）部分集合について、条件をすべてみたすような組み合わせがないならば答えが \(0\) になることは明らかです。そうでないとき、条件をみたす \(A\) が少なくとも \(1\) つ存在します。この場合、条件に登場しない \(A_j\) を任意の非負整数に変えてもやはり条件をみたします。よって、この場合答えは無数に存在します。

実装上の方針としてはいくつか考えられ、\(dp[i][S]\%998244353\) とは別に \(dp[i][S]>0\) かどうかをフラグとして持っておくほか、\(T_i\) を \(dp[i][S]>0\) なる集合について、\((S,dp[i][S]\%998244353)\) の集合として定義し、これを更新するようにし、\(T_{30}\) に \(((0,0,.\ldots,0),*)\) が含まれるか判定するなどの方法があります。いずれの方針でも、計算量への影響は極めて軽微です。

C++ による実装例

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

#define ll long long
#define rep(i, n) for(int i = 0; i < n; ++i)
#define N (int)8
#define MOD (ll)998244353

int n,k;
int d[N][N]; //whether A_j exist in the left side of i-th re-arranged constaint
ll s[N]; //S'_j

vector<int>a[1<<8]; //3k(max.24)bit
vector<ll>c[1<<8];  //count

void pre_calc(void){
	unordered_map<int,int>tmp[1<<8];
	rep(bits,1<<n){
		int x[8]={};
		int y=0,z=0;
		rep(i,k){
			rep(j,n){
				if(d[i][j]==1)x[i]+=(bits>>j)&1;
			}
		}
		rep(j,k){
			y|=(x[j]&1)<<j; //k bit
			z|=(x[j]>>1)<<(j*3); //3k bit
		}
		tmp[y][z]=tmp[y][z]+1;
	}
	rep(i,1<<k){
		unordered_map<int,int>::iterator itr=tmp[i].begin();
		while(itr!=tmp[i].end()){
			a[i].push_back((*itr).first);
			c[i].push_back((*itr).second);
			itr++;
		}
	}
	return;
}




int main(void){
	int tmpl,tmpr;
	ll tmps;
	int m;
	int base[N+1];
	ll offset[N+1];

	//receive input
	cin>>n>>m;

	rep(i,n+1){
		base[i]=i;
		offset[i]=0;
	}

	rep(i,m){
		cin>>tmpl>>tmpr>>tmps;
		tmpl--;
		tmps-=(tmpr-tmpl); //Ai: positive -> non-negative
		if(tmps<0){
			cout<<"0"<<endl;
			return 0;
		}
		if(base[tmpl]==base[tmpr]){
			if(offset[tmpr]-offset[tmpl]!=tmps){
				cout<<"0"<<endl;
				return 0;
			}
		}
		int overwrite_before, overwrite_after;
		ll add_offset;
		if(base[tmpl]<base[tmpr]){
			overwrite_before=base[tmpr];
			overwrite_after=base[tmpl];
			add_offset=offset[tmpl]-offset[tmpr]+tmps;
		}
		else{
			overwrite_before=base[tmpl];
			overwrite_after=base[tmpr];
			add_offset=offset[tmpr]-offset[tmpl]-tmps;
		}
		rep(j,n+1){
			if(base[j]==overwrite_before){
				base[j]=overwrite_after;
				offset[j]+=add_offset;
			}
		}
	}

	//set re-arranged constraints
	int x[30][8];  //x[i][j] i-th bit of S'_j
	bool used[8]={}; //check for the existence of un-constrained Ai
	k=0; //M'
	rep(i,N)rep(j,N)d[i][j]=0;
	rep(i,n){
		for(int j=i+1;j<=n;j++){
			if(base[i]==base[j]){
				if(offset[j]-offset[i]<0){
					cout<<"0"<<endl;
					return 0;
				}
				for(int ii=i;ii<j;ii++){
					d[k][ii]=1;
					used[ii]=true;
				}
				s[k]=offset[j]-offset[i];
				for(int ii=0;ii<30;ii++)x[ii][k]=(s[k]>>ii)&1;
				k++;
				break;
			}
		}
	}

	pre_calc();

	vector<int>dpkey={0}; //3k bit
	vector<ll>dpcnt={1};
	rep(i,30){
		int sz=dpkey.size();
		unordered_map<int,ll>mp;
		rep(j,sz){
			int y[8]={};
			rep(ii,k)y[ii]=(dpkey[j]>>(3*ii))&1;
			int pre=0; //3k bit
			rep(ii,k)pre|=(dpkey[j]>>1)&(3<<(3*ii));
			int add_key=0;//k bit
			rep(ii,k){
				add_key|=(x[i][ii]^y[ii])<<ii;
				if((x[i][ii]==0)&&(y[ii]==1))pre+=1<<(3*ii);
			}
			int sz2=a[add_key].size();
			rep(ii,sz2){
				mp[a[add_key][ii]+pre]=mp[a[add_key][ii]+pre]+(c[add_key][ii]*dpcnt[j]);
			}
		}
		dpkey.clear();
		dpcnt.clear();
		unordered_map<int,ll>::iterator itr=mp.begin();
		while(itr!=mp.end()){
			dpkey.push_back((*itr).first);
			dpcnt.push_back((*itr).second%MOD);
			itr++;
		}
	}

	//judge zero/non-zero and get remainder
	bool found=false;
	ll ans=0;
	int sz=dpkey.size();
	rep(i,sz){
		if(dpkey[i]==0){
			found=true;
			ans=dpcnt[i];
		}
	}
	if(found){
		rep(i,n){
			if(!used[i]){
				cout<<"Infinity"<<endl;
				return 0;
			}
		}
		cout<<ans<<endl;
	}
	else{
		cout<<0<<endl;
	}
	
	return 0;
}