#include <cstdio>
#include <vector>

using namespace std;

typedef struct rectangle{
    int width,height;
    bool horizontal=false,vertical= false,placed=false;
    int urc [2],ulc[2],brc[2],blc[2];

}Rectangle;

typedef struct point{
    int x,y;
}Point;
void vertical_coordinates(Rectangle *array_rec, int sq,int blcx,int blcy);
void horizontal_coordinates(Rectangle *array_rec, int sq,int blcx,int blcy);
void possibilities(Rectangle *array_rec,int n_rectangles, int*solutions, long* area,vector<Point> &occupied_points,int num_inits,int i);
long total_height=0,total_width=0;
int init_times=0;

int main() {

    long area=0;

    int solutions=0;
    int n_rectangles=0; /*nº de rectangulos no input*/
    vector <Point> occupied_points;

    scanf("%d",&n_rectangles);
    Rectangle array_rec[n_rectangles]; /* array que guarda as medidas de cada rectangulo*/
    for(int i=0;i<n_rectangles;i++){
        fscanf(stdin,"%d %d",&array_rec[i].width,&array_rec[i].height);
        if(array_rec[i].width==array_rec[i].height){
            init_times++;
        }
        else{
            init_times+=2;
            printf("init %d",init_times);
        }
        area+=(array_rec[i].width*array_rec[i].height);

    }
    printf("area:%ld",area);

    possibilities(array_rec,n_rectangles,&solutions,&area,occupied_points,0,0);
    printf("%d",solutions);
    return 0;
}

void vertical_coordinates(Rectangle *array_rec, int sq,int blcx,int blcy) {
    array_rec[sq].blc[0] = blcx;
    array_rec[sq].blc[1] = blcy;
    array_rec[sq].brc[0] = array_rec[0].width;
    array_rec[sq].brc[1] = blcy;
    array_rec[sq].ulc[0] = blcx;
    array_rec[sq].ulc[1] = array_rec[0].height;
    array_rec[sq].urc[0] = array_rec[0].width;
    array_rec[sq].urc[1] = array_rec[0].height;
}

void horizontal_coordinates(Rectangle *array_rec, int sq,int blcx,int blcy) {
    array_rec[sq].blc[0] = blcx;
    array_rec[sq].blc[1] = blcy;
    array_rec[sq].brc[0] = array_rec[0].height;
    array_rec[sq].brc[1] = blcy;
    array_rec[sq].ulc[0] = blcx;
    array_rec[sq].ulc[1] = array_rec[0].width;
    array_rec[sq].urc[0] = array_rec[0].height;
    array_rec[sq].urc[1] = array_rec[0].width;
}


void possibilities(Rectangle *array_rec,int n_rectangles, int*solutions, long* area,vector<Point> &occupied_points,int num_inits,int i) {

    if(num_inits==init_times){
        return;
    }
    int placed=0;
    for(int s=0;s<n_rectangles;s++){
        if(array_rec[s].placed){
            placed++;
            array_rec[s].placed=false;
        }
    }
    if(placed==n_rectangles){
        num_inits=0;
        i=0;
        *solutions+=1;
    }
    if (n_rectangles == 1){
        if (array_rec[0].height == array_rec[0].width){
            *solutions = 1;
            return;
        }
        else{
            *solutions=2;
            return;
        }
    }
    else {
            if(!array_rec[i].vertical){
                if(occupied_points.empty()) {
                    if(array_rec[i].vertical){
                        array_rec[i].horizontal=true;
                        horizontal_coordinates(array_rec,i,0,0);

                    }
                    else {
                        array_rec[i].vertical = true;

                        vertical_coordinates(array_rec, i,0,0);
                    }
                    Point point1={array_rec[i].ulc[0],array_rec[i].ulc[1]};
                    Point point2={array_rec[i].brc[0],array_rec[i].brc[1]};
                    occupied_points.push_back(point1);
                    occupied_points.push_back(point2);
                    total_height+=array_rec[i].height;
                    total_width+=array_rec[i].width;
                    array_rec[i].placed=false;
                    possibilities(array_rec,n_rectangles,solutions,area,occupied_points,num_inits+1,i+1);


                }
                else{
                    for(int j=0;j<(int)occupied_points.size();j++) {
                        if((total_height+array_rec[i].height)*(total_width)<*area)  {
                            vertical_coordinates(array_rec, i, occupied_points.at((unsigned long)j).x,occupied_points.at((unsigned long)j).y);
                            array_rec[i].vertical=true;
                            total_height+=array_rec[i].height;
                            occupied_points.erase(occupied_points.begin()+j);
                            Point point1={array_rec[i].ulc[0],array_rec[i].ulc[1]};
                            Point point2={array_rec[i].brc[0],array_rec[i].brc[1]};
                            occupied_points.push_back(point1);
                            occupied_points.push_back(point2);
                            possibilities(array_rec,n_rectangles,solutions,area,occupied_points,num_inits,i+1);

                        }
                        else if((total_width+array_rec[i].width)*(total_height)<*area)  {
                            horizontal_coordinates(array_rec, i, occupied_points.at((unsigned long)j).x,occupied_points.at((unsigned long)j).y);
                            array_rec[i].horizontal=true;
                            total_width+=array_rec[i].width;
                            occupied_points.erase(occupied_points.begin()+j);
                            bool add=true;
                            Point point1={array_rec[i].ulc[0],array_rec[i].ulc[1]};

                            for(int h=0;h<(int)occupied_points.size();h++){
                                if(occupied_points.at((unsigned long)h).x==point1.x || occupied_points.at((unsigned long)h).y==point1.y){
                                    add=false;
                                    break;
                                }
                            }
                            if(add){
                                occupied_points.push_back(point1);

                            }
                            Point point2={array_rec[i].brc[0],array_rec[i].brc[1]};
                            for(int h=0;h<(int)occupied_points.size();h++){
                                if(occupied_points.at((unsigned long)h).x==point2.x || occupied_points.at((unsigned long)h).y==point2.y){
                                    add=false;
                                    break;
                                }
                            }
                            if(add){
                                occupied_points.push_back(point2);

                            }
                            possibilities(array_rec,n_rectangles,solutions,area,occupied_points,num_inits,i+1);
                        }
                    }
                }
            }
        }
    }