IOI2017 Camp. C

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define mp make_pair
#define pb push_back

constexpr int N = (int)1e6 + 111;
constexpr int md = (int)1e9+7;
constexpr int INF = (int)2e9;
constexpr int inv6 = 175000002;
constexpr double eps = 1e-7;
constexpr double LOG2_3 = log2((double)3);

//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")

void add(int& a,int b){
    a = (a + b >= md ? a + b - md : a + b);
}

class myInt{
public:
    int cnt2, cnt3;
    bool is_negative, is_zero;
    bool lessZero() const{
        return is_negative;
    }
    bool lessEqualZero() const{
        return is_negative || is_zero;
    }
    bool biggerZero() const{
        return !is_negative && !is_zero;
    }
    bool biggerEqualZero() const{
        return !is_negative;
    }
    /// if is_zero, then is_negative = false
public:
    myInt():cnt2(0),cnt3(0),is_negative(false),is_zero(false){
        cnt3 = 0;
        is_negative = true;
    }
    myInt(int x):cnt2(0),cnt3(0),is_negative(false),is_zero(false){
        if(x == 0)
            is_zero = true;
        else if(x < 0)
            is_negative = true;
        if(abs(x) == 2)
            cnt2 = 1;
        else if(abs(x) == 3)
            cnt3 = 1;
    }
    myInt(const myInt& other){
        this->cnt2 = other.cnt2;
        this->cnt3 = other.cnt3;
        this->is_negative = other.is_negative;
        this->is_zero = other.is_zero;
    }
    myInt& operator=(const myInt& other){
        this->cnt2 = other.cnt2;
        this->cnt3 = other.cnt3;
        this->is_negative = other.is_negative;
        this->is_zero = other.is_zero;
        return *this;
    }
    friend
    bool operator<(const myInt& a,const myInt& b){
        if(a.lessZero() && b.biggerEqualZero()){
            return true;
        }
        if(a.lessEqualZero() && b.biggerZero()){
            return true;
        }
        if(a.biggerEqualZero() && b.lessEqualZero()){
            return false;
        }
        if(a.lessEqualZero() && b.lessEqualZero()){
            return (a.cnt2-b.cnt2) - (b.cnt3 - a.cnt3) * LOG2_3 > eps;
        } else {
            return (a.cnt2-b.cnt2) - (b.cnt3 - a.cnt3) * LOG2_3 < eps;
        }
    }
    bool operator>(const myInt& other){
        if(lessEqualZero() && other.biggerEqualZero()) /// <= 0 ? >= 0
            return false;
        if(biggerEqualZero() && other.lessZero()) /// >= 0 && < 0
            return true;
        if(lessEqualZero() && other.lessEqualZero()){
            return (cnt2-other.cnt2) - (other.cnt3 - cnt3) * LOG2_3 < eps;
        } else {
            return (cnt2-other.cnt2) - (other.cnt3 - cnt3) * LOG2_3 > eps;
        }
    }
    friend
    myInt operator*(const myInt& a,const myInt& b){
        myInt result = a;
        result.cnt2 += b.cnt2;
        result.cnt3 += b.cnt3;
        result.is_negative ^= b.is_negative;
        result.is_zero |= b.is_zero;
//        if(result.is_zero){
//            result.is_zero = true;
//            result.cnt2 = result.cnt3 = 0;
//            result.is_negative = false;
//        }
        return result;
    }
    friend
    istream& operator>>(istream& o,myInt& x){
        int value;
        o >> value;
        x = myInt(value);
        return o;
    }
    int getValue(){
        if(is_zero) return 0;
        int x = 1;
        for(int i = 0; i < cnt2; i++) x = (1ll * x * 2) % md;
        for(int i = 0; i < cnt3; i++) x = (1ll * x * 3) % md;
        if(is_negative) x = md - x;
        return x;
    }
};

myInt a[501][501];
myInt dp[2][501][501];

myInt st[2][10][501];
int n,m,k;

myInt getMin(int l,int r){
    l = max(1ll,l);
    r = min(m,r);
    int j = __lg(r - l + 1);
    return min(st[1][j][l],st[1][j][r-(1<<j)+1]);
}

myInt getMax(int l,int r){
    l = max(1ll,l);
    r = min(m,r);
    int j = __lg(r - l + 1);
    return max(st[0][j][l],st[0][j][r-(1<<j)+1]);
}

void solve(){
//    assert(myInt(-3) < myInt(3));
//    assert(myInt(-2) < myInt(3));
//    assert(myInt(-1) < myInt(3));
//    assert(myInt(0) < myInt(3));
//    assert(myInt(1) < myInt(3));
//    assert(myInt(2) < myInt(3));
//    assert(!(myInt(3) < myInt(3)));
//
//    assert((myInt(2)*myInt(2)).getValue() == 4);
//    assert((myInt(2)*myInt(3)).getValue() == 6);
//    assert((myInt(-2)*myInt(3)).getValue() == md-6);
//
//    return;
    cin >> n >> m >> k;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }
//
//    for(int i = 1; i <= n; i++){
//        for(int j = 1; j <= m; j++){
//            cout << a[i][j].getValue() << " ";
//        }
//        cout << "\n";
//    }

    for(int t = 0; t < 2; t++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                dp[t][i][j].cnt3 = n+1;
                dp[t][i][j].is_negative = !t;
            }
        }
    }

    for(int i = 1; i <= m; i++){
        dp[0][1][i] = dp[1][1][i] = a[1][i];
    }

    for(int i = 2; i <= n; i++){
        for(int j = 1; j <= m; j++){
            st[0][0][j] = dp[0][i-1][j];
            st[1][0][j] = dp[1][i-1][j];
        }
        for(int t = 1; t < 10; t++){
            for(int j = 1; j + (1 << t) - 1 <= m; j++){
                st[0][t][j] = max(st[0][t-1][j],st[0][t-1][j+(1<<(t-1))]);
                st[1][t][j] = min(st[1][t-1][j],st[1][t-1][j+(1<<(t-1))]);
            }
        }
        for(int j = 1; j <= m; j++){
            myInt maxVal = getMax(j-k,j+k);
            myInt minVal = getMin(j-k,j+k);
            if(dp[0][i][j] < maxVal * a[i][j]) dp[0][i][j] = maxVal * a[i][j];
            if(dp[0][i][j] < minVal * a[i][j]) dp[0][i][j] = minVal * a[i][j];
            if(dp[1][i][j] > maxVal * a[i][j]) dp[1][i][j] = maxVal * a[i][j];
            if(dp[1][i][j] > minVal * a[i][j]) dp[1][i][j] = minVal * a[i][j];
        }
    }

//    for(int i = 1; i <= n; i++){
//        for(int j = 1; j <= m; j++){
//            cout << dp[1][i][j].getValue() << " ";
//        }
//        cout << "\n";
//    }

    myInt maxVal = dp[0][n][1];
    for(int i = 1; i <= m; i++){
        maxVal = max(maxVal,dp[0][n][i]);
    }
    cout << maxVal.getValue() << "\n";

    return;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
//  freopen("output.txt","w",stdout);
    int tests = 1;
    cin >> tests;
    for(int test = 1; test <= tests; test++){
//        cout << "Case #" << test << ": ";
        solve();
    }
    return 0;
}
/**
2

1
2
2 1

3

1
2
3
2 1
3 1
3 2
2 3

3 1 -> phi(3) = 2
3 2


**/