1411: 马的摆放

这是一道关于国际象棋棋盘上放子的题目， 虽然这种题目已经出滥了， 但是大家还是要忍住再摆一回"马"吧 :-), 这里面马的攻击规则和传统的国际象棋一样, 即一个坐标是(0,0)的马可以攻击到的格子是(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2), 假设这些格子都在棋盘上。 这道题的描述非常简单, 就是在n*n(1≤n≤10)的棋盘上放k个马, 问有多少种摆放的方法使得任意两个马互相不攻击. 唯一的限制是你只能把这些马摆放到指定的t(k≤t≤40)个位置上。为了简化你的输出, 你只要输出结果除以9901的余数就可以了。

输入的第一行是包含三个整数n、t、k, 之后t行每行两个整数x和y( 1≤x≤n, 1≤y≤n)描述每个可以放置马的位置, 这里面任意两个位置都是不同的.

输出总共的放置方案数除以9901的余数。

2 4 2
1 1 
1 2 
2 1 
2 2 

6