Ruudukko

#include <iostream>
#include <algorithm>
#include <stack>
 
using namespace std;
 
typedef unsigned int intu;
 
int main() {
	const int MOD = 1e9 + 7;
	// size
	int size;
	cin >> size;
	const int size2 = size * size;
	// order of boxes
	auto *order = new pair<int,pair<int,int>>[size2];
	// input to boxes
	int i;
	int cord = 0;
	for (int y=0; y < size; y++) {
		for (int x=0; x < size; x++) {
			cin >> i;
			order[cord++] = {i, {x, y}};
		}
	}
	// preparation
	intu total_paths = 0;
	intu row1[size] = {};
	intu row2[size] = {};
	sort(order, order + size2);
	// helping stuff
	intu cpath;
	stack<pair<intu,int>> s1;
	stack<pair<intu,int>> s2;
	pair<int,pair<int,int>> p;
	pair<intu,int> s;
	// main check
	for (int i=0; i < size2 - 1; i++) {
		p = order[i];
		cpath = row1[p.second.first] + row2[p.second.second] + 1;
		// same number next -> save new rows
		if (order[i + 1].first == p.first) {
			s1.push({cpath, p.second.first});
			s2.push({cpath, p.second.second});
		}
		// new number next -> update every row
		else {
			row1[p.second.first] = (row1[p.second.first] + cpath) % MOD;
			row2[p.second.second] = (row2[p.second.second] + cpath) % MOD;
			while (!s1.empty()) {
				s = s1.top();
				row1[s.second] = (row1[s.second] + s.first) % MOD;
				s = s2.top();
				row2[s.second] = (row2[s.second] + s.first) % MOD;
				s1.pop();
				s2.pop();
			}
		};
		// add to total count
		total_paths += cpath;
		total_paths %= MOD;
	}
	// last path
	p = order[size2 - 1];
	total_paths += row1[p.second.first] + row2[p.second.second] + 1;
	total_paths %= MOD;
	// result
	cout << total_paths << "\n";
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 2, 3

Verdict: ACCEPTED

Test 5

Group: 2, 3

Verdict: ACCEPTED

Test 6

Group: 2, 3

Verdict: ACCEPTED

Test 7

Group: 3

Verdict: ACCEPTED

Test 8

Group: 3

Verdict: ACCEPTED

Test 9

Group: 3

Verdict: ACCEPTED