Description

这又是一道关于国际象棋棋盘上放子的题目， 虽然这种题目已经出滥了， 但是大家还是要忍住再摆一回"马"吧 :-), 这里面马的攻击规则和传统的国际象棋一样, 即一个坐标是(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 的余数就可以了

Format

Input

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

Output

唯一的一行一个整数表示总共的放置方案数除以 9901 的余数.

Samples

2 4 2
1 1
1 2
2 1
2 2

6

Limitation

1s, 1024KiB for each test case.