#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define itr ::iterator
typedef pair<int,int> pii;
const int MAX=1e6;
const int mod=1e9;
ll res1,res2,sum[MAX];
int DistanceSum(int N, int *X, int *Y)
{
int f=X[0],s=Y[0],f_=X[0],s_=Y[0];
for(int A=1;A<N;A++)
{
f=max(f,X[A]);
s=max(s,Y[A]);
f_=min(f_,X[A]);
s_=min(s_,Y[A]);
}
f=f-f_+1;
s=s-s_+1;
for(ll A=1;A<MAX;A++)
sum[A]=(sum[A-1]+A)%mod;
for(ll A=1;A<=f;A++)
{
res1+=((s*s)%mod*(sum[A-1]))%mod;
res1%=mod;
}
for(ll A=1;A<=s;A++)
{
res2+=((f*f)%mod*sum[A-1])%mod;
res2%=mod;
}
return (res1+res2)%mod;
}
/*signed main()
{
ios_base::sync_with_stdio(false);
int X[]={2,2,3,3,4,4,4,4,5,5,5};
int Y[]={5,6,3,6,3,4,5,6,3,4,6};
cout<<DistanceSum(11,X,Y);
return 0;
}*/
