题目描述

Eli 在翻看童年照片时，看到一张她和另外 N-1 位朋友排成一列、每人放着一只风筝的照片。可惜，Eli 已经不记得哪只风筝属于哪位朋友了，而照片里风筝线又太细，看不出哪个孩子牵着哪只风筝。她唯一记得的是：风筝线彼此没有交叉，否则就会缠在一起并掉到地上。

现在 Eli 想知道：一共有多少种可能的风筝对应关系。也就是说，能有多少种不同的方法，使得每个孩子各牵一只风筝，并且所有风筝线都既不相交也不接触。

我们把每个孩子表示为平面上的点 (Ci, 0)（因为他们站在地面上），把每只风筝表示为点 (Xi, Yi)（因为风筝在空中飞）。某个孩子所牵风筝的线，就是连接该孩子坐标与对应风筝坐标的线段。

Eli 实际上关心的是：有多少个风筝排列 P，使得如果第 i 个孩子牵的是第 Pi 只风筝，那么由此形成的任意两条线段都不会相交或接触。

请编写程序 kites，求出满足条件的排列个数。

输入格式

第一行包含一个整数 N，表示孩子和风筝的数量。

第二行包含 N 个整数 Ci，表示每个孩子在 x 轴上的位置。

接下来 N 行，每行两个整数 Xi 和 Yi，表示每只风筝的坐标。

输出格式

输出一行一个整数，表示合法配置的数量。

由于答案可能很大，请输出它对 1 000 000 007 取模后的结果。

数据范围

• 1 ≤ N ≤ 50
• 1 ≤ Ci, Xi, Yi ≤ 5000
• 所有点（无论是孩子还是风筝）两两不同。

样例

输入

5
42 13 17 5 666
77 13
19 101
55 82
1 80
55 133

输出

3