【问题描述】

给定一个有向图 G=(V,E)。给每个结点 v 赋上权值 w[v]（w[v]须为正整数），使得对于任意一个结点 v∈V，都有 w[v]=sum{w[u]}((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