时间限制：1秒　　内存限制：256M

---

【题目描述】

　　在一个 \(N * N\) 的棋盘上，放置 \(N\) 个车，某些位置不能放，一旦 \((x,y)\) 格子放置一个车后，其同行、同列不能再放车了（即棋盘上的车不能相互攻击），请你合法的放置方案数 \(mod\ 123456789\)。

【输入格式】

　　第一行一个整数 \(N\)，表示棋盘大小（行列都从 1 开始编号）。接下来的若干行，每行两个整数：\(x\ y\)，表示，棋盘的 \(x\) 行 \(y\) 里不能放车，以 \(0\ 0\) 结束输入。

【输出格式】

　　一个整数，合法放置方案 \(mod\ 123456789\) 的结果。

【输入输出样例】

　Input

2
1 1
0 0

　Output

1

【数据限制】

　　对于 \(100\%\) 的数据，对于全部数据，\(1≤N≤20\)。

【来源】

　　Mr.he