시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 1024 MB321100.000%

문제

Giving in to the lobby of the International Toddlers Association, and with the full support of the International Exhausted Parents Association, the 2024 Olympic Committee decided to inaugurate the Toddlers Olympics, a special and massively attended event.

The Wooden Blocks Stacking contest is one of the main trials thereof, intended towards dramatically challenging contestants’ strength, patience, and hand-to-eye coordination.

For this contest, participants are given $N$ equal-depth wooden blocks $B_1, B_2, \dots , B_N$, having integer height and width (measured in centimetres). The purpose of the contest is to obtain a complete stack containing all of these $N$ blocks. The winner is the toddler achieving this truly impressive result in the least amount of time. To build the complete stack, contestants are allowed to build partial stacks, i.e., stacks containing consecutive blocks $B_i , B_{i+1}, \dots , B_j$ from bottom to top, in that order; in particular, each block is a partial stack containing exactly one block, and a stack is complete when it contains all the blocks. Moreover, the contestants must comply with the following rules:

  • Stacks are built against a wall. Thus, when placing the block $B_{i+1}$ on top of the block $B_i$, both blocks are perfectly aligned depth-wise, with their front and back borders perfectly aligned. Moreover, the left border of $B_{i+1}$ must be either perfectly aligned with the left border of $B_i$, or shifted left or right by an integer amount of centimetres.
  • At each step, participants must place a partial stack containing blocks $B_j , B_{j+1}, \dots , B_k$ on top of another partial stack containing blocks $B_i , B_{i+1}, \dots , B_{j-1}$.
  • Each (partial or complete) stack ever formed must be stable: a stack containing the blocks $B_i , B_{i+1}, \dots , B_j$ is stable if, for any block $B_k$ such that $i \le k \le j - 1$, the center of gravity of the sub-stack formed by the blocks $B_{k+1} , \dots , B_j$ does not project strictly outside of the block $B_k$.

You have somehow managed to get the dream job of surveillance assistant in the Wooden Blocks Stacking trial. Although the contest is in itself intense and exciting, your tireless brain issues an additional challenge: you wonder, given the sequence of $N$ blocks, how many possible configurations can be obtained for the complete stack? Since this may be a very large number, you further wish to count these configurations modulo the prime number $1\, 000\, 000\, 007$.

입력

The first line contains the number $N$. This line is followed by $N$ lines, which describe the $N$ wooden blocks, starting from block $1$ and up to block $N$. The $i$th such line contains two space-separated integers $w_i$ and $h_i$; $w_i$ is the width of the block $i$, and $h_i$ is its height.

출력

The output should contain a single line, consisting of an integer representing the number of distinct stable complete stacks that can be obtained by stacking the input blocks, modulo $1\, 000\, 000\, 007$.

제한

  • $1 \le N \le 200$
  • $1 \le w_i \le 10$ and $1 \le h_i \le 10$ for all $i \le N$.

예제 입력 1

3
2 3
3 2
4 1

예제 출력 1

8

Given the three blocks provided as input, a contestant can build the 8 distinct configurations depicted below.

Among these configurations, the first six can be achieved by progressively stacking single blocks on top of an increasing partial stack.

The last two require, in order to maintain stability at all steps, the construction of a partial stack with blocks $2$ and $3$, then the placement of this partial stack on top of block $1$.

예제 입력 2

2
1 1
5 1

예제 출력 2

1