幼儿园的游戏

幼儿园的游戏

测试数据来自 system/1953

描述

公元1770年,纪昀先生途经进香河,与百姓谈说人世,谈说友善。他所告诉人们的为友之道,流传至今,深深影响着当地的人们,甚至是幼儿园的孩童。

一天,多诺达新幼儿园的孩子们与老师们排排坐,形成了一个N*M的矩形队列,一共有K个老师,他们融入在了这个矩形队列之中,与小朋友们欢乐地唱着歌。“手拉手,我们永远都是好朋友!”于是老师要求每一位小朋友都和四周(即上下左右四个方向)的任意两个小朋友牵手。

作为幼儿园里最聪明的小朋友,你马上意识到这并不是单纯的游戏,而是一个非常有意义的问题。你非常希望知道一共有多少种不同的牵手方案,满足每一位小朋友都可以和四周恰好两位小朋友牵手。当然,每一位小朋友都只能和小朋友牵手,不能去和老师牵手。任何一位小朋友都不允许自己和自己牵手(即左手拉右手)。

你所需要知道的只是方案个数,因为答案可能太大,所以需要对1000000007取模。

格式

输入格式

第一行有三个整数,分别是N,M和K。如题目中所描述的一样。

之后有K行,每一行有2个整数x和y,描述了一位老师的位置。

输出格式

你只需要输出一个整数,表示答案关于1000000007取模后的结果。

样例1

样例输入1

3 6 2
2 2
2 5

样例输出1

3

样例2

样例输入2

2 4 0

样例输出2

2

限制

对于5%的数据,N,M<=5
对于25%的数据,N<=6,M<=3500
对于60%的数据,N<=6,M<=2147483647
对于100%的数据,N<=8,M<=2147483647,K<=100
其中有15%的数据,K=0

提示

样例说明(样例数据一)

图片

来源

JSOI 2012 round3 day1

信息

ID
1964
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者