2228: 和图
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
给定一个有向图 G=(V,E)。给每个结点v 赋上权值w[v]（w[v]须为正整数），使得对于任意一个结点v∈V，都有w[v]=sum{w}((u,v) ∈ E)。则得到的加权图就是一个“和图”。如图（结点中的数字表示该结点权值）：图G 共有n 个结点，从1~n 标号。图中可能有自环、重边。其中某个结点x的权值w[x]已经固定，求可得到的满足“和图”条件的加权图的个数。
输入
输入第一行为两个正整数 n,m，分别表示图G 中的结点数和有向边数。
接下来的 m 行，每行有两个正整数u,v，表示图G 中的一条有向边(u,v)。
最后一行是两个正整数 x,w[x]。
输出
输出包括一行：如果可得到的“和图”有无穷多个，输出inf；否则输出其个数（须对10008取模）。
样例输入 复制
3 2
1 2
3 2
2 5样例输出 复制
4提示
【数据范围】
对于 100%的数据1≤n≤15,1≤m≤100,w[x]≤100,000。