求跳abcG

#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize(3)
#pragma GCC optimize(2)
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;
//#undef ONLINE_JUDGE
#define int long long

void clear() {
}

int n, m, dp[500005], dp2[500005], l[500005], r[500005]; 
/* Yet another rongchi problem?
 考虑 dp[i] 表示计数以 i 开头的合法方案数量
 那么我们就会大力进行转移
 这样就会把连续类的算进来，也就是不合法的
 为了去除，我们需要容斥
 我们考虑这个连续段会连续到哪里
 然后再来计数
 但是这样或许不利于方案数的计量
 先试试  
 不会算重的吧
 嗯哼算重了
 我们考虑到，直接计算会包含以下情形：
 xxxxoooooo
 而不会包含：
 xxxxxxoooo
 因为这是我们对于合法的定义
 也就是只有第一个不合法的？
 我们考虑别样的计数，例如，另外计数一个东西表示任意搞的方案数量
 那么就可以 i 的任意搞的值减去 i+2 任意搞的值？
 这对吗
 xxxxxxooooooxxxxoo
 这个东西会被消除
 xxooooooooooxxxxoo
 这个不会被消除，这不符合预期
 所以还是应该为 dp[i+2] - ...
 所以应该是 -1 ^ i 状物，这不是我们想看见的，因为非常棍母
 首先通过一些神秘东西去掉
 然后滚木消失了一半
 于是可能就需要大力 ds 了
 好的
*/
const int p = 998244353;
int cnt1[500005], cnt2[500005], rsum[500005], r2sum[4][2];
vector<pair<int, int>> edges[500005];
void solve() {
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		cin >> l[i] >> r[i];
		edges[l[i]].push_back({r[i], -1});
		edges[r[i]].push_back({r[i], 1});
		cnt2[r[i]]++;
		cnt2[l[i]]--;
	}
	dp[n + 1] =1;
	dp2[n + 1] = 1;
	int nowcnt = 0;
	for (int i = n; i >= 1; --i) {
		int ans = dp[i + 1];
		int cnt = 0;
		/*
		for (int j = 1; j <= m; ++j) {
			if (l[j] <= i && i + 1 <= r[j]) {
				if (((r[j]+1-i)/2)%2) ans += dp2[((r[j] + 2) + ((r[j]+1)%2==i%2))];
				else ans -= dp2[((r[j] + 2) + ((r[j]+1)%2==i%2))];
			}
		}*/
		int j = 0;
		
		ans += r2sum[(i + 1)%4][0];
		ans += r2sum[(i + 2)%4][1];
		ans -= r2sum[(i + 3)%4][0];
		ans -= r2sum[(i + 4)%4][1];
	/*	
		for (r[j] = i; r[j] <= n; ++r[j]) {
			if (r[j] % 4 == (i+1) % 4)
				ans += dp2[(r[j] + 2) + 1] * rsum[r[j]];
			else if (r[j] % 4 == (i+2) % 4) 
				ans += dp2[(r[j] + 2)] * rsum[r[j]];
			else if (r[j] % 4 == (i+3) % 4) 
				ans -= dp2[(r[j] + 2) + 1] * rsum[r[j]];
			else 
				ans -= dp2[(r[j] + 2)] * rsum[r[j]];
		}*/
		cnt = nowcnt;
		ans += (dp[i + 2] - dp2[i + 4]) * cnt % p;
		nowcnt += cnt2[i];
		for (auto j : edges[i]) {
			rsum[j.first] += j.second ;
			(r2sum[j.first % 4][1] += dp[j.first + 2] * j.second) %= p;
			(r2sum[j.first % 4][0] += dp[j.first + 3] * j.second) %= p;
		}
		dp[i] = ans % p;
		dp2[i] = (dp[i] - dp2[i + 2]) % p;
	}
	cout << (dp[1]%p+p)%p << "\n";
}


signed main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;
//	cin >> tc;
	while (tc--) {
		clear();
		solve();
	}
	return 0;
}