我loj上最慢的点4s，但是你谷上大部分都在7s以上QAQ

#include <bits/stdc++.h>

typedef long long ll;
const int SIZE = 3000 + 10;
const int mod = 1e9 + 7;

ll QuickPower(int a, int k, int P) {
	int result = 1, base = a % P;
	while (k) {
		if (k & 1)
			result = 1ll * result * base % P;
		base = 1ll * base * base % P;
		k >>= 1;
	}
	return result;
}

int N, Q;
int matrix[SIZE][SIZE];
int to[4];

int IdSum, id[SIZE][SIZE];

class Node {
public:
	int value[4];
	int toId[4], from[4];
	// toId 0去左边 1去上边 2去右边 3去下边
	// from[i] 表示当这个点去往i方向时，去往的内个点连向这个点的方向
}node[SIZE * SIZE];

class Temp {
public:
	int first;
	int second;
	int third;
};

int add(int x, int y) {
	return (x + y) > mod ? x + y - mod : x + y;
}

int del(int x, int y) {
	return (x - y < 0) ? x - y + mod : x - y;
}

void Next(Temp &a) {
	int temp = a.first;
	a.first = node[temp].toId[to[a.third]];
	a.second = add(a.second, node[temp].value[to[a.third]]);
	a.third = node[temp].from[to[a.third]];
}

void Get(Temp &result, int begin, int direct, int l, int r) {
	// int now = node[begin].toId[direct];
	// int from = node[begin].from[direct];
	// int value = node[begin].value[direct];
	result = {node[begin].toId[direct], node[begin].value[direct], node[begin].from[direct]};

	if (direct == 2 || direct == 3) {
		for (int i = 1; i <= N; ++ i) {
			if (l <= i && i <= r) 
				return;
			
			// if (i > r)
			// 	return;
			
			Next(result);
		}
	}
	else {
		for (int i = N; i >= 1; -- i) {
			if (l <= i && i <= r) {
				// vector = {now, value, from};
				return;
			}

			// if (i < l)
			// 	return;
			
			Next(result);
		}
	}
}

Temp pos[2][4];

void Rotate(int x1, int x2, int y1, int y2) {
	Get(pos[0][0], id[0][y1 - 1], 3, x1, x2);
	Get(pos[0][1], id[x1 - 1][N + 1], 0, y1, y2);
	Get(pos[0][2], id[N + 1][y2 + 1], 1, x1, x2);
	Get(pos[0][3], id[x2 + 1][0], 2, y1, y2);

	Get(pos[1][0], id[0][y1], 3, x1, x2);
	Get(pos[1][1], id[x1][N + 1], 0, y1, y2);
	Get(pos[1][2], id[N + 1][y2], 1, x1, x2);
	Get(pos[1][3], id[x2][0], 2, y1, y2);

	int len = x2 - x1 + 1;
	for (int i = 0; i <= 3; ++ i) {
		for (int j = 0; j < len; ++ j) {
			Temp outside = pos[0][i];
			Temp inside = pos[1][(i + 1) % 4];
			int direct1 = (outside.third + 1) % 4, direct2 = (inside.third - 1 + 4) % 4;
			
			node[outside.first].toId[direct1] = inside.first;
			node[outside.first].value[direct1] = del(inside.second, outside.second);
			node[outside.first].from[direct1] = direct2;

			node[inside.first].toId[direct2] = outside.first;
			node[inside.first].value[direct2] = del(outside.second, inside.second);
			node[inside.first].from[direct2] = direct1;

			Next(pos[0][i]);
			Next(pos[1][(i + 1) % 4]);
		}
	}
}

void Add(int x1, int x2, int y1, int y2, int w) {
	Get(pos[0][0], id[0][y1 - 1], 3, x1, x2);
	Get(pos[0][1], id[x1 - 1][N + 1], 0, y1, y2);
	Get(pos[0][2], id[N + 1][y2 + 1], 1, x1, x2);
	Get(pos[0][3], id[x2 + 1][0], 2, y1, y2);

	Get(pos[1][0], id[0][y1], 3, x1, x2);
	Get(pos[1][1], id[x1][N + 1], 0, y1, y2);
	Get(pos[1][2], id[N + 1][y2], 1, x1, x2);
	Get(pos[1][3], id[x2][0], 2, y1, y2);

	int len;
	for (int i = 0; i <= 3; ++ i) {
		if (i == 0 || i == 2)
			len = x2 - x1 + 1;
		else
			len = y2 - y1 + 1;
		for (int j = 0; j < len; ++ j) {
			Temp outside = pos[0][i];
			Temp inside = pos[1][i];
			int direct1 = (outside.third + 1) % 4, direct2 = (inside.third - 1 + 4) % 4;

			node[outside.first].value[direct1] = add(node[outside.first].value[direct1], w);

			node[inside.first].value[direct2] = del(node[inside.first].value[direct2], w);

			Next(pos[0][i]);
			Next(pos[1][i]);
		}
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);

	// freopen("matrix.in", "r", stdin);
	// freopen("matrix.out", "w", stdout);

	std::cin >> N >> Q;
	for (int i = 0; i <= N + 1; ++ i) {
		for (int j = 0; j <= N + 1; ++ j) {
			id[i][j] = ++ IdSum;
		}
	}
	to[0] = 2, to[1] = 3, to[2] = 0, to[3] = 1;

	for (int i = 1; i <= N; ++ i) 
		for (int j = 1; j <= N; ++ j) 
			matrix[i][j] = QuickPower(i + 1, j, 998244353);
		

	for (int i = 0; i <= N + 1; ++ i) {
		for (int j = 0; j <= N + 1; ++ j) {
			int now = id[i][j];
			if (j != 0) {
				node[now].toId[0] = id[i][j - 1];
				node[now].from[0] = to[0];
				node[now].value[0] = del(matrix[i][j - 1], matrix[i][j]);
			}
			if (i != 0) {
				node[now].toId[1] = id[i - 1][j];
				node[now].from[1] = to[1];
				node[now].value[1] = del(matrix[i - 1][j], matrix[i][j]);
			}
			if (j != N + 1) {
				node[now].toId[2] = id[i][j + 1];
				node[now].from[2] = to[2];
				node[now].value[2] =  del(matrix[i][j + 1], matrix[i][j]);
			}
			if (i != N + 1) {
				node[now].toId[3] = id[i + 1][j];
				node[now].from[3] = to[3];
				node[now].value[3] = del(matrix[i + 1][j], matrix[i][j]);
			}
		}
	}

	int opt, x1, y1, x2, y2, d;
	while (Q --) {
		std::cin >> opt >> x1 >> y1 >> x2 >> y2;
		if (opt == 1) {
			Rotate(x1, x2, y1, y2);
		}
		else {
			std::cin >> d;
			Add(x1, x2, y1, y2, d);
		}
	}

	int answer = 0;
	for (int i = 1; i <= N; ++ i) {
		Get(pos[0][0], id[i][0], 2, 1, N);
		// for (int j = 1; j <= N; ++ j)
		// 	matrix[i][j] = line[0][0].array[j - 1].second % mod;
		for (int j = 1; j <= N; ++ j) {
			answer = add(answer, pos[0][0].second * QuickPower(12345, (i - 1) * N + j, mod) % mod);
			Next(pos[0][0]);
		}
	}
	std::cout << answer << '\n';

	return 0;
}
/*
10 10
2 5 1 10 4 689412516
1 3 4 3 4
1 3 5 4 6
1 4 1 8 5
1 1 2 1 2
1 4 2 7 5
1 2 5 2 5
2 3 3 3 9 856075030
2 4 2 5 6 308750020
2 1 5 9 7 252732904
*/