#include <bits/stdc++.h>

using namespace std;

struct point {
  long long x, y, z;
  long long dist(const point &other) {
    return abs(x - other.x) + abs(y - other.y) + max(0LL, other.z - z);
  }
};

const long long LLINF = (long long) 1e18;
long long dp[22][1 << 22];

int main() {
  int N;
  cin >> N;
  vector<point> p(N);
  for (int i = 0; i < N; i++) {
    cin >> p[i].x >> p[i].y >> p[i].z;
  }

  for (int i = 0; i < 22; i++) for (int j = 0; j < (1 << 22); j++) {
    dp[i][j] = LLINF;
  }

  dp[0][0] = 0;
  for (int b = 0; b < (1 << N); b++) {
    for (int cur = 0; cur < N; cur++) {
      if (dp[cur][b] == LLINF) continue;

      for (int nxt = 0; nxt < N; nxt++) {
        if (b & (1 << nxt)) continue;

        const auto nxt_bit = b | (1 << nxt);
        dp[nxt][nxt_bit] = min(dp[nxt][nxt_bit], dp[cur][b] + p[cur].dist(p[nxt]));
      }
    }
  }

  cout << dp[0][(1 << N) - 1] << endl;
}


/*  Jai Shree Ram 🚩🚩🚩 */
#include "bits/stdc++.h"
#define ll long long int
#define oo 1000000000000000000
#define forr(i,n) for(int i=0;i<n;i++)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()
#define unique(v) sort(all(v)); v.resize(distance(v.begin(),unique(all(v))))
#define eb emplace_back
#define FF first
#define SS second
#define mem(a,v) memset(a,v,sizeof(a))
#define pb push_back
#define popcount(x) __builtin_popcount(x)

using namespace std;

template<typename T>
ostream &operator<<(ostream &output,const vector<T> &v){ 
    if(v.empty()) return output;
    for(int i=0;i<v.size()-1;i++) output << v[i] <<" ";
    output << v.back();
    return output;
}
template<typename T>
istream &operator>>(istream &input,vector<T> &v){ 
    for(auto &i: v) cin >> i;
    return input;            
}
const int N = 3005 , mod = 1e9 + 7;
int best[N][N];
int n;
ll dp[N][N];

ll get(int i,int k){
    if( i > n) return 0;
    else if(best[i][k] == n+1) return 1;
    else if(best[i][k] == n+2) return 0;
    else if(dp[i][k]!=-1) return dp[i][k];
    else{
        ll ans = 0;
        ans += get(best[i][k] , k + 1);
        ans %= mod;
        ans += get(best[i][k] , k);
        ans %= mod;
        return dp[i][k] = ans;
    }
}

void __sol(){
    cin >> n;
    vector<ll> v(n); cin >> v;
    forr(i,n+3) forr(j,n+3) best[i][j] = n+2;
    mem(dp,-1);
    for(int k=1;k<=n;k++){
        vector<int> seen(k,-1);
        ll sum = 0;
        seen[0] = n + 1;
        for(int j=n;j>=1;j--){
            sum += v[j-1]%k;
            sum %= k;
            if(seen[sum]!=-1) best[j][k] = seen[sum];
            seen[sum] = j;
        }
    }
    cout << get(1,1)<<"\n";
    return;
}


int main(){ 
    fastio;
    int tc=1;  // cin >> tc;
    while(tc--) __sol();
    return 0;
}