Description

Calculus is the first lesson Jason had. It is tedious, so an interesting idea occurred to Jason. He took out his mobile phone and open the HDUOJ and found a water problem. He said to himself, “I must solve this f**king easy water problem in ten minutes! ”.

You were invited to compete with him online. Don’t be defeated.

Input

Multiple test cases, Each test first contains an integer N(3<=N<=100000) indicating the number of vertices of the polygon. The i-th of the following N lines contains two integers xi and yi (0<=xi,yi<=10^9) separated by a blank. (xi,yi) is the i-th vertex of the polygon, and (x1,y1),...,(xn,yn) will be in counterclockwise order.

Output

For each test case, output a number as the answer which is the area of the polygon be multiplied by 2. In case the answer is greater than 1000000006, please modulo the answer with 1000000007.

Sample Input

3
0 0
1 0
0 1
4
0 0
1 0
1 1
0 1

Sample Output

1
2

多边形每个边两个端点跟原点组成的三角形，它们的面积有正有负，所有面积之和就是多边形的面积。 

负数取模注意：(a%mod+b%mod+mod)%mod;

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const int N=1e5+30;

struct point
{
    ll x,y;
} s[N];
ll n;

int main()
{
    while(~scanf("%lld",&n))
    {
        memset(s,0,sizeof(s));
        for(int i=1; i<=n; i++)
        {
            scanf("%lld%lld",&s[i].x,&s[i].y);
        }
        s[n+1]=s[1];
        ll ans=0;
        for(int i=2; i<=n+1; i++)
        {
            ans=(ans+(s[i-1].x*s[i].y-s[i].x*s[i-1].y)%mod+mod)%mod;
        }
        cout<<ans<<'\n';
    }
    return 0;
}