#P2751. [HAOI2012]容易题(easy)

[HAOI2012]容易题(easy)

题目描述

为了使得大家高兴,小 Q 特意出个自认为的简单题来满足大家,这道简单题描述如下:

有一个数列 aa,已知对于所有的 aia_i 都是 [1,n][1,n] 之间的自然数,并且知道对于一些 aia_i 不能取哪些值,我们定义一个数列的积为该数列所有元素的乘积。

要求你求出所有可能的数列的积的和  mod (109+7)\bmod (10^9+7) 的值,是不是很简单呢?呵呵!

输入格式

第一行三个整数 n,m,kn,m,k,分别表示数列元素的取值范围,数列元素个数,以及已知的限制条数。 接下来 kk 行,每行两个正整数 x,yx,y 表示 axa_x 的值不能是 yy。

输出格式

一行一个整数表示所有可能的数列的积的和对 109+710^9+7 取模后的结果。

3 4 5
1 1
1 1
2 2
2 3
4 3
90

数据规模与约定

对于 30%30\% 的数据 n≤4n\leq 4,m≤10m\leq 10,k≤10k\leq 10。 另有 20%20\% 的数据 k=0k=0。 对于 70%70\% 的数据 n≤103n\leq 10^3,m≤103m\leq 10^3,k≤103k\leq 10^3。 对于 100%100\% 的数据 n≤109n\leq 10^9,m≤109m\leq 10^9,k≤105k\leq 10^5,1≤y≤n1\leq y\leq n,1≤x≤m1\leq x\leq m。