인형의 계보

Inventive and Creative Puppets Corporation(ICPC)는 어린이를 위한 교육용 $인형$을 여러 종류로 판매하고, 예전에 어린이였고 지금도 그 시절을 기억하는 어른을 위한 인형도 판매한다. 창립 100주년을 기념하여 ICPC는 100년 역사에서 특히 인기가 많았던 인형을 모은 컬렉션을 판매하기로 했다. 수집가들이 틀림없이 부러워할 컬렉션이다.

각 인형의 머리에는 고리가 달려 있어, 다른 인형의 두 발가락 중 하나에 걸 수 있다. 한 발가락에는 최대 한 개의 인형만 걸린다. 인형은 거꾸로 서는 자세를 불편해하므로 인형의 고리(루프)는 허용하지 않는다. 모든 인형을 다른 인형의 발가락에 걸고, 가장 위의 인형의 고리만 벽에 걸면 $트리$가 만들어진다.

각 인형은 자식 수의 최솟값과 최댓값이 따로 정해져 있다. 인형에 자식이 있다면 그중 적어도 한 명은 부모보다 출시일이 늦어야 한다. 자식이 두 명이면 한 명은 부모보다 출시일이 빨라도 된다.

이 규칙을 만족하는 서로 다른 트리의 개수를 구하라. 어떤 인형이 다른 부모에 걸리거나, 같은 부모의 다른 발가락에 걸리면 두 트리는 서로 다른 트리이다.

입력은 다음 형식의 테스트케이스 하나로 주어진다.

$n$ $x_1$ $y_1$ ... $x_n$ $y_n$

첫 줄에는 인형의 수 $n$ ($2 \le n \le 300$)이 주어진다. 이어지는 $n$개의 줄은 출시일이 오래된 순서대로 나열된 인형을 하나씩 설명하며, $i$번째 줄에는 그 인형의 자식 수 최솟값 $x_i$와 최댓값 $y_i$가 주어진다. 단, $0 \le x_i \le y_i \le 2$이다.

규칙을 만족하는 트리의 개수를 한 줄에 출력한다. 답은 $10^9 + 7$로 나눈 나머지로 출력한다.

샘플 입력 1에서는 그림 G.1에 나타난 6개의 트리가 규칙을 만족한다.

샘플 입력 2에서는 규칙을 만족하는 트리가 없다.

그림 G.1. 샘플 입력 1에서 규칙을 만족하는 트리. 인형의 숫자는 출시 순서이다.