/*
 * @Author: Luisvacson
 * @LastEditors: Luisvacson
 * @Descriptions: None
 * @Date: 2021-06-12 19:05:10
 * @LastEditTime: 2021-06-12 19:38:21
 * @FilePath: \C++\Public\ABC203D - Pond.cpp
 */
#include <bits/stdc++.h>
using namespace std;

int n, k, t;
int a[805][805], b[805][805];
int sum[805][805];

inline bool check(int mid) {
    register int i, j;
    memset(b, 0, sizeof(b));
    memset(sum, 0, sizeof(sum));

    for (i = 1; i <= n; ++i) {
        for (j = 1; j <= n; ++j) {
            if (a[i][j] > mid) b[i][j] = 1;
        }
    }

    for (i = 1; i <= n; ++i) {
        for (j = 1; j <= n; ++j) {
            sum[i][j] =
                sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + b[i][j];
        }
    }

    for (i = 0; i <= n - k; ++i) {
        for (j = 0; j <= n - k; ++j) {
            if ((sum[i + k][j + k] + sum[i][j] - sum[i][j + k] -
                 sum[i + k][j]) < t)
                return true;
        }
    }
    return false;
}

signed main() {
    scanf("%d%d", &n, &k);
    t = ((k * k) >> 1) + 1;
    register int i, j;
    int l = 0, r = 0, mid, ans = 0;

    for (i = 1; i <= n; ++i) {
        for (j = 1; j <= n; ++j) {
            scanf("%d", &a[i][j]);
            r = max(r, a[i][j]);
        }
    }

    while (l <= r) {
        mid = l + r >> 1;
        if (check(mid)) {
            r = mid - 1;
            ans = mid;
        } else
            l = mid + 1;
    }

    printf("%d\n", ans);
    return 0;
}
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define mp make_pair
#define fr first
#define sc second

template<class T> T T_INF(){ return 1000000000000000000; }
template<> int T_INF<int>(){ return 1000000000; }

template<int MOD> struct modint{
	ull val;
	modint(ull x){ val=x%MOD; }
	modint(){}
	friend modint modpow(modint x,ull k){
		modint ret(1ULL);
		while(k>0){
			if(k&1ULL)ret*=x;
			x*=x;
			k>>=1;
		}
		return ret;
	}
	modint& operator +=(const modint& rhs){
		this->val+=rhs.val;
		if(this->val>=MOD)this->val-=MOD;
		return *this;
	}
	friend modint operator+(modint lhs, const modint& rhs){
		lhs+=rhs;
		return lhs;
	}
	modint& operator -=(const modint& rhs){
		this->val+=MOD-rhs.val;
		if(this->val>=MOD)this->val-=MOD;
		return *this;
	}
	friend modint operator-(modint lhs, const modint& rhs){
		lhs-=rhs;
		return lhs;
	}
	modint& operator *=(const modint& rhs){
		this->val*=rhs.val;
		this->val%=MOD;
		return *this;
	}
	friend modint operator*(modint lhs, const modint& rhs){
		lhs*=rhs;
		return lhs;
	}
	static vector<modint> inv_;
	static void precalc_inv_(int k){
		int t=inv_.size();
		inv_.resize(k);
		for(int i=t;i<k;i++){
			inv_[i]=modpow(modint(i),MOD-2);
		}
	}
	modint& operator /=(const modint& rhs){
		//if(rhs.val<inv_.size()){
		//	(*this)*=inv_[rhs.val];
		//}
		//else {
			(*this)*=modpow(rhs,MOD-2);
		//}
		return *this;
	}
	friend modint operator/(modint lhs, const modint& rhs){
		lhs/=rhs;
		return lhs;
	}
	
	static vector<vector<modint>> C_;
	static vector<modint> fac,inv_fac;
	static void precalc_C_(int k){
		C_.resize(k,vector<modint>(k));
		for(int i=0;i<k;i++){
			C_[i][0]=C_[i][i]=1;
			for(int j=1;j<=i-1;j++){
				C_[i][j]=C_[i-1][j-1]+C_[i-1][j];
			}
		}
	}
	static void precalc_fac(int k){
		fac.resize(k);
		inv_fac.resize(k);
		fac[0]=inv_fac[0]=1;
		for(int i=1;i<k;i++){
			fac[i]=fac[i-1]*i;
			inv_fac[i]=modpow(fac[i],MOD-2);
		}
	}
	static modint C(ll n,ll k,int type=0){
		if(k<0||k>n)return 0;
		if(type==0){
			return C_[n][k];
		}
		else {
			return fac[n]*inv_fac[k]*inv_fac[n-k];
		}
	}
};
template<int MOD> vector<modint<MOD>> modint<MOD>::inv_;
template<int MOD> vector<vector<modint<MOD>>> modint<MOD>:: C_;
template<int MOD> vector<modint<MOD>> modint<MOD>::fac;
template<int MOD> vector<modint<MOD>> modint<MOD>::inv_fac;

const int MOD=1000000007;
typedef modint<MOD> mi;

int n;
int a[100010];

mi dp[100010][2];

mi f(int i){
	if(i==-2)return 0;
	if(i<=0)return 1;
	return dp[i][0]+dp[i][1];
}

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",&a[i]);
	
	dp[1][0]=dp[1][1]=1;
	for(int i=2;i<100010;i++){
		dp[i][0]=dp[i-1][0]+dp[i-1][1];
		dp[i][1]=dp[i-1][0];
	}
	
	mi ret=0;
	for(int i=0;i<n;i++){
		ret+=f(i-1)*f(n-1-i)*a[i];
		ret-=f(i-2)*f(n-2-i)*a[i];
	}
	cout<<ret.val<<endl;
}