2754.D - R2T4 路径的值(graph)

## 题目描述

嫣嫣正走在一张图上。这张图上有$n$个点，并且有$m$条单向连边。

嫣嫣惊讶地发现，这张图上的点都有些不同寻常。具体而言，这些点上都写着一个符号（加号`+`或者乘号$`*$`）和一个正整数。嫣嫣还发现，这张图是一张有向无环图（$DAG$），也就是说，如果从图上任意一个点出发，永远都不可能回到这个点本身。

嫣嫣心里默念着数字 $0$ ，然后蹦蹦跳跳地在这张图上走着。她通过$m$条单向连边中的若干条，按照顺序到访了若干点（注意，点不允许重复经过）。

嫣嫣突然有一个问题想要请问你：如果她可以从任一点出发，不重复地走过若干个点，并且在任一点结束自己的行程。每到一个新的点（包括出发点和到达点）时，嫣嫣会把自己心理默念的数字加上或者乘上这个正整数。比如，嫣嫣依次经过了标记了 $`+3, *4, +5$` 的点，那么嫣嫣心理默念的数字会依次变成$ 3，12，173，12，17$。嫣嫣想要知道，在所有的行程方案中，最后嫣嫣心里默念的数字恰好为$q$的方法有多少？

注意，对于两个行程，如果行程的长度一致，并且两个行程依次经过的点都一样，那么认为这两个行程方案是同一种方案。更规范化的：假如第$1$种行程方案依次经过的点的编号是：$x_1,x_2,x_3,...,x_p$，第$2$种行程方案依次经过的点的编号是：$y_1,y_2,y_3,...,y_q$，那么只有在$p=q,x_1=y_1,x_2=y_2,...,x_p=y_qp=q,$的时候，这两种行程方案被视作相同。

## 输入格式

第$1$行，$3$个整数：$n,m,q$

第$2$行，$n$个符号和一个一位正整数的组合（比如$`+3,*5$`），使用空格分隔，其中第$i$个整数或符号表示第$i$个点上写的内容。

之后$m$行，每行$2$个整数$u_i v_i$，表示从$u_i$有一条连向$v_i$的边。题目保证，这张图一定是一张有向无环图。

本题共420$个测试点，其中：

数据点$1-3$保证，$1\le n \le 10, 1\le m \le 20,1\le q \le 10$，同时保证第$2$行出现的符号均为正号。

数据点$4-6$保证，$1\le n \le 15, 1\le m \le 30, 0\le q \le 10$。

数据点$7-12$保证，$1\le n \le 100, 1\le m \le 1000, 1\le q \le 40$，同时保证第$2$行出现的符号均为正号。

数据点$13-20$保证，$1\le n \le 10000, 1\le m \le 100000, 0\le q \le 5000$。

## 输出格式

$1$行，$1$个整数，表示满足题意的方案数。由于答案可能很大，请输出答案对$10^9+7$取余数的结果。

## 输入
```in1
5 7 2
+1 *2 *2 +1 *2
1 2
2 3
3 4
4 5
1 3
2 4
3 5
```

## 输出
```out1
6
```

## 提示