2184. 雕塑安置

【题目描述】

话说SYZX为了美化校园，请设计师设计了n座精美的雕塑，准备安置在校园里。整个校园可以抽象为一个n*n 的大网格，并且为了平均分布这些雕塑，学校决定网格的同一行、同一列必须有且只有一座雕塑，还规定不能出现1座以上的雕塑出现在同一个1*1 网格里的情况。然而某些1*1 的网格恰巧是一片湖或者是食堂，这些网格就不能安置雕塑了。每个雕塑的造型是相同的，这样同一种安置方案中交换排列都算一种。

学校想知道有多少种安置方案，你能解决这个问题吗？

【输入格式】

第一行两个整数n,m 用空格分开,n表示n*n的大网格，m表示不能安置雕塑的位置个数。

第二行至第m+1行，每行两个整数x,y，用空格分开，表示坐标（x,y）的1*1 网格上不能安置雕塑。

【输出格式】

仅一行，方案的个数。

【样例输入】

6 7
1 1
2 1
2 2
3 3
3 4
4 3
4 4

【样例输出】

184

【提示】

对于 50%的数据， 保证 n≤10,m≤10

对于100%的数据，保证n≤20,m≤10，方案总数≤2^63-1

【来源】

在此键入。