显然考虑 DP，两种思路：

• 记录 i 选的数量，i-1 选的数量。

• 记录 $[i-1, i, i+1]$ 的数量，$[i, i+1, i+2]$ 的数量。

两种都可以做，但是写一写基础 DP 方程就会发现第一种比较麻烦，于是优先考虑第二种。

• 令 $f[i][j][k]$ 表示前 i 个数中，选了 j 个 $[i, i+1, i+2]$，k 个 $[i-1, i, i+1]$。

• 显然 $f[i][j][k]$ 由 $f[i-1][k][l]$ 转移过来。

• 考虑一下系数，应为每种情况可能的 $(i, i, i)$ 的数量，即 $\lfloor \dfrac{C-已选 i 的数量}{3}\rfloor = \lfloor\dfrac{C-j-k-l}{3}\rfloor$ 。

• 至于有限制的，稍微改改即可。

考虑优化：

• 首先，若形如 $[i-1, i, i+1]$ 的数量超过 2，则一定可以改成若干个 $(i, i, i)$ 的形式 + 几个 $[i-1, i, i]$。

  • 所以 $j,k,l<3$。

• 其次，大部分（除了给出的那 X 个）$f[i]$ 的转移是一样的，所以考虑矩阵快速幂。

  • 对于有值的那一部分单独 DP 即可。

Code：

#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;

const int MOD = 998244353;

class Matrix {
private:
public:
	int N, M; ll a[10][10];
	inline void init(int C) {
		// printf("init(%d)\n", C);
		N = 9, M = 9;
		for(int i=0; i<9; i++) {
			for(int j=0; j<9; j++) {
				if(i%3 != j/3)	continue;
				int s = i/3 + i%3 + j%3;
				if(s <= C)	a[i][j] = (C - s)/3 + 1;
				// printf("a[%d][%d]:%lld, s:%d\n", i, j, a[i][j], s);
			}
		}
		// puts("");
	}
	inline void init() {
		N = 1, M = 9, a[0][0] = 1;
	}
	inline void init(int C, int num) {
		N = 9, M = 9;
		for(int i=0; i<9; i++) {
			for(int j=0; j<9; j++) {
				if(i%3 != j/3)	continue;
				int s = i/3 + i%3 + j%3;
				if(s < num)	s += (num-s+2)/3*3;
				if(s <= C)	a[i][j] = (C-s)/3+1;
				else 	a[i][j] = 0;
			}
		}
		// printf("init(%d, %d)\n", C, num);
		// for(int i=0; i<N; i++) {
		// 	for(int j=0; j<M; j++) {
		// 		printf("a[%d][%d]:%lld\n", i, j, a[i][j]);
		// 	}
		// }
		// puts("");
	}
	inline int ans() {
		return a[0][0];
	}
	static inline void mul(Matrix &a, Matrix &b) {
		static ll c[10][10];
		// printf("a.N:%d, a.M:%d, b.N:%d, b.M:%d\n", a.N, a.M, b.N, b.M);
		for(int i=0; i<a.N; i++) {
			for(int j=0; j<b.M; j++) {
				c[i][j] = 0;
				for(int k=0; k<a.M; k++) {
					c[i][j] += a.a[i][k]*b.a[k][j] %MOD;
				}
				c[i][j] %= MOD;
			}
		}
		for(int i=0; i<a.N; i++) {
			for(int j=0; j<a.M; j++) {
				a.a[i][j] = c[i][j];
			}
		}
	}
} c, f, tmp;

namespace Josh_zmf {
	
	ll N; int C, X;

	inline void pow(Matrix &c, Matrix a, ll b) {
		// printf("pow(%lld)\n", b);
		for(; b; ) {
			if(b&1)	Matrix::mul(c, a);
			Matrix::mul(a, a), b >>= 1;
		}
	}

	inline int main() {
		cin>> N>> C>> X;
		c.init(C), f.init();
		// for(int i=0; i<9; i++) {
		// 	for(int j=0; j<9; j++) {
		// 		printf("f[%d][%d]:%lld\n", i, j, f.a[i][j]);
		// 	}
		// }
		int last = 0;
		for(int i=1, num; i<=X; i++) {
			ll id; cin>> id>> num;
			if(id != last+1)	pow(f, c, id-last-1);
			// for(int j=0; j<9; j++) {
			// 	for(int k=0; k<9; k++) {
			// 		printf("f[%d][%d]:%lld, tmp:%lld\n", j, k, f.a[j][k], tmp.a[j][k]);
			// 	}
			// }
			tmp.init(C, num), Matrix::mul(f, tmp), last = id;
		}
		pow(f, c, N-last);
		cout<< f.ans()<< '\n';
		return 0;
	}

}

signed main() {
	Josh_zmf::main();
	return 0;
}