This time our child has a simple polygon. He has to find the number of ways to split the polygon into non-degenerate triangles, each way must satisfy the following requirements:

  * each vertex of each triangle is one of the polygon vertex; 
  * each side of the polygon must be the side of exactly one triangle; 
  * the area of intersection of every two triangles equals to zero, and the sum of all areas of triangles equals to the area of the polygon; 
  * each triangle must be completely inside the polygon; 
  * each side of each triangle must contain exactly two vertices of the polygon. 



The picture below depicts an example of a correct splitting.

<image>

Please, help the child. Calculate the described number of ways modulo 1000000007 (109 + 7) for him.

Input

The first line contains one integer n (3 ≤ n ≤ 200) — the number of vertices of the polygon. Then follow n lines, each line containing two integers. The i-th line contains xi, yi (|xi|, |yi| ≤ 107) — the i-th vertex of the polygon in clockwise or counterclockwise order.

It's guaranteed that the polygon is simple.

Output

Output the number of ways modulo 1000000007 (109 + 7).

Examples

Input

4
0 0
0 1
1 1
1 0


Output

2


Input

4
0 0
1 0
0 1
-1 0


Output

1


Input

5
0 0
1 0
1 1
0 1
-2 -1


Output

3

Note

In the first sample, there are two possible splittings:

<image>

In the second sample, there are only one possible splitting:

<image>
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.math.BigInteger;
import java.util.Collections.*;
import java.util.function.Consumer;

import static java.lang.Math.*;
import static java.lang.Math.min;
import static java.util.Arrays.*;
import static java.math.BigInteger.*;


public class Main{

    void run(){
        Locale.setDefault(Locale.US);
        boolean my;
        try {
            my = System.getProperty("MY_LOCAL") != null;
        } catch (Exception e) {
            my = false;
        }
        try{
            err = System.err;
            if( my ){
                sc  = new FastScanner(new BufferedReader(new FileReader("input.txt")));
//                sc  = new FastScanner(new BufferedReader(new FileReader("C:\\myTest.txt")));
                out = new PrintWriter   (new FileWriter("output.txt"));
            }
            else {
                sc = new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
                out = new PrintWriter(new OutputStreamWriter(System.out));
            }
//            out = new PrintWriter(new OutputStreamWriter(System.out));
        }catch(Exception e){
            MLE();
        }
        if( my )
            tBeg = System.currentTimeMillis();
        solve();
        if( my )
            err.println( "TIME: " + (System.currentTimeMillis() - tBeg ) / 1e3 );
        exit(0);
    }

    void exit( int val ){
        err.flush();
        out.flush();
        System.exit(val);
    }

    double tBeg;
    FastScanner sc;
    PrintWriter out;
    PrintStream err;

    class FastScanner{

        StringTokenizer st;
        BufferedReader br;

        FastScanner( BufferedReader _br ){
            br = _br;
        }

        String readLine(){
            try {
                return br.readLine();
            } catch (IOException e) {
                return null;
            }
        }

        String next(){
            while( st==null || !st.hasMoreElements() )
                st = new StringTokenizer(readLine());
            return st.nextToken();
        }

        int nextInt(){ return Integer.parseInt(next()); }
        long nextLong(){ return Long.parseLong(next()); }
        double nextDouble(){ return Double.parseDouble(next()); }
    }

    void MLE(){
        int[][] arr = new int[1024*1024][]; for( int i = 0; i < 1024*1024; ++i ) arr[i] = new int[1024*1024];
    }

    void MLE( boolean doNotMLE ){ if( !doNotMLE ) MLE(); }

    void TLE(){
        for(;;);
    }

    public static void main(String[] args) {
        new Main().run();
//        new Thread( null, new Runnable() {
//            @Override
//            public void run() {
//                new Main().run();
//            }
//        }, "Lolka", 256_000_000L ).run();
    }

    ////////////////////////////////////////////////////////////////

    class Pt{
        long x, y;
        Pt( long _x, long _y ){
            x = _x;
            y = _y;
        }

        public Pt sub(Pt p) {
            return new Pt(x-p.x, y-p.y);
        }

        public long VP(Pt p) {
            return x * p.y - y*p.x;
        }
    }

    int n;
    Pt[] arr;
    long[][] dp;
    final long mod = (int)1e9 + 7;
    long[][][] sq;
    Random rnd = new Random(1212);

    long getDP( int i, int j ){
        if( dp[i][j] != -1 )
            return dp[i][j];

        long ans = 0;
        if( i+1==j ){
            ans = 1;
        }
        else if( i < j ){
            ans = 0;
//            if( good(i,i+1,j) )
//                ans = getDP( i+1, j );
            for (int k = i+1; k <= j-1; k++) {
                if( good(i,k,j) )
                    ans = (ans + getDP(i,k)*getDP(k,j)%mod) % mod;
            }
        }
        else MLE();

        return dp[i][j] = ans;
    }

    private boolean good(int i, int k, int j) {
        boolean ans = true;
        long[] sq_ij = sq[i][j];
        long[] sq_ik = sq[i][k];
        long[] sq_kj = sq[k][j];
        long s = abs(sq[i][k][j]);
        for (int p = 0; p < n; p++) {
            if( p == i ) continue;
            if( p == k ) continue;
            if( p == j ) continue;
            if( abs(sq_ij[p])+abs(sq_ik[p])+abs(sq_kj[p]) == s ){
                ans = false;
                break;
            }
        }
        return ans;
    }

    void solve(){
        n = sc.nextInt();
//        n = 200;
        arr = new Pt[n];
        for (int i = 0; i < n; i++) {
            arr[i] = new Pt(sc.nextInt(),sc.nextInt());
//            arr[i] = new Pt(i,5 + rnd.nextInt(100_000));
        }
//        arr[0] = new Pt(0,0);
//        arr[n-1] = new Pt(n-1,0);

        sq = new long[n][n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    sq[i][j][k] = arr[i].sub(arr[k]).VP( arr[j].sub(arr[k]) );
                    sq[i][j][k] = abs( sq[i][j][k] );
                }
            }
        }

        dp = new long[n][n];
        for (long[] d : dp) {
            fill( d, -1 );
        }
        out.println( getDP(0,n-1) );
    }




}