Ruudukko

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N =1e5;
const int inf = 1e9;
const ll mod = 1e9 + 7;



int main(){


    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int> (n));
    vector<pair<int, pair<int, int>>> m;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            cin >> a[i][j]; 
            m.push_back({a[i][j], {i, j}});
        }
    }
    sort(m.begin(), m.end());
    vector<vector<ll>> ans(n, vector<ll> (n));
    vector<ll> cols(n), rows(n);
    ll sum = 0;
    int pre = 1, prei = 0;
    for(int i = 0; i < n * n; ++i){


        auto [val, p] = m[i];

        if(val != pre){
            pre = val;
            for(int j = prei; j < i; ++j){
                auto [val2, p2] = m[j];
                int y = p2.first, x = p2.second;
                sum+=ans[y][x];
                sum%=mod;
                cols[x]+=ans[y][x];
                cols[x]%=mod;
                rows[y]+=ans[y][x];
                rows[y]%=mod;
            }
            prei = i;
        }

        int y = p.first, x = p.second;
        ans[y][x] = 1;

        ans[y][x] += cols[x];
        ans[y][x] %= mod;        
        
        ans[y][x] += rows[y];
        ans[y][x] %= mod;
    }    
    for(int i = prei; i < n * n; ++i){
        auto [val, p] = m[i];
        int y = p.first, x = p.second;
        sum+=ans[y][x];
        sum%=mod;
    }


    cout << sum << "\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