#4531. [Bjoi2014]路径

题目描述

在一个N个节点的无向图（没有自环、重边）上，每个点都有一个符号，

可能是数字，也可能是加号、减号、乘号、除号、小括号。你要在这个图上数

一数，有多少种走恰好K个节点的方法，使得路过的符号串起来能够得到一

个算数表达式。路径的起点和终点可以任意选择。

所谓算数表达式，就是由运算符连接起来的一系列数字。括号可以插入在

表达式中以表明运算顺序。

注意，你要处理各种情况，比如数字不能有多余的前导0，减号只有前面

没有运算符或数字的时候才可以当成负号，括号可以任意添加（但不能有空括

号），0可以做除数（我们只考虑文法而不考虑语意），加号不能当正号。

例如，下面的是合法的表达式：

-0/0

((0)+(((23+4)+(-5)+7))+(-(23)*6))

而下面的不是合法的表达式：

001+0

1+2(2)

3+-3

--1

+1

()

输入格式

第一行三个整数N,M,K，表示点的数量，边的数量和走的节点数。

第二行一个字符串，表示每个点的符号。

接下来M行，每行两个数，表示一条边连的两个点的编号。

1≤N≤20，0≤M≤N×(N-1)/2，0≤K≤30

输出格式

输出一行一个整数，表示走的方法数。这个数可能比较大，你只需要输出

它模1000000007的余数即可。

样例

样例输入

6 10 3  

)(1*+0  

1 2  

1 3  

1 4  

2 3  

3 4  

2 5  

3 5  

3 6  

4 6  

5 6

样例输出

10  

//一共有10条路径，构成的表达式依次是101, (1), 1+1, 1+0, 1*1, 1*0, 0+0,  

0+1, 0*0, 0*1

数据范围与提示